Un jugador de cricket tiene que anotar N carreras, con la condición de que solo pueda tomar 1 o 2 carreras y que las carreras consecutivas no sean 2. Encuentre todas las combinaciones posibles que puede tomar.
Ejemplos:
Input : N = 4 Output : 4 1+1+1+1, 1+2+1, 2+1+1, 1+1+2 Input : N = 5 Output : 6
Fuente: Entrevista de Oracle en el campus
Este problema es una variación de contar el número de formas de alcanzar la puntuación dada en un juego y puede resolverse en tiempo O(n) y espacio auxiliar constante.
La primera carrera anotada podría ser:
a) 1. Ahora el jugador tiene que anotar N-1 carreras.
b) o 2. Dado que los 2 no pueden ser carreras consecutivas, la próxima carrera anotada debe ser 1. Después de eso, el jugador debe anotar N-(2+1) carreras.
A continuación se muestra la solución recursiva del problema anterior.
La relación de recurrencia sería:
ContarVías(N) = ContarVías(N-1) + ContarVías(N-2)
La siguiente solución recursiva toma tiempo y espacio exponencial (similar a los números de Fibonacci).
C++
// A simple recursive implementation for
// counting ways to reach a score using 1 and 2 with
// consecutive 2 allowed
#include <iostream>
using namespace std;
int CountWays(int n)
{
// base cases
if (n == 0) {
return 1;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 1 + 1;
}
// For cases n > 2
return CountWays(n - 1) + CountWays(n - 3);
}
// Driver code
int main()
{
int n = 10;
cout << CountWays(n);
return 0;
}
Java
// A simple recursive implementation for
// counting ways to reach a score using 1 and 2 with
// consecutive 2 allowed
import java.io.*;
class GFG {
static int CountWays(int n)
{
// base cases
if (n == 0) {
return 1;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 1 + 1;
}
// For cases n > 2
return CountWays(n - 1) + CountWays(n - 3);
}
// Driver code
public static void main(String[] args)
{
int n = 5;
System.out.println(CountWays(n));
}
}
Python3
# A simple recursive implementation for # counting ways to reach a score using 1 and 2 with # consecutive 2 allowed def CountWays(n): # base case if n == 0: return 1 if n == 1: return 1 if n == 2: return 1 + 1 # For cases n > 2 return CountWays(n - 1) + CountWays(n - 3) # Driver code if __name__ == '__main__': n = 5 print(CountWays(n))
C#
// A simple recursive implementation
// for counting ways to reach a score
// using 1 and 2 with consecutive 2 allowed
using System;
class GFG {
static int CountWays(int n)
{
// base cases
if (n == 0) {
return 1;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 1 + 1;
}
// For cases n > 2
return CountWays(n - 1) + CountWays(n - 3);
}
// Driver Code
static public void Main()
{
int n = 5;
Console.WriteLine(CountWays(n));
}
}
PHP
<?php
// A simple recursive implementation
// for counting ways to reach a score
// using 1 and 2 with consecutive 2 allowed
function CountWays($n)
{
// base cases
if ($n == 0) {
return 1;
}
if ($n == 1) {
return 1;
}
if ($n == 2) {
return 1 + 1;
}
// For cases n > 2
return CountWays($n - 1) + CountWays($n - 3);
}
// Driver Code
$n = 5;
echo CountWays($n);
?>
Javascript
<script>
// A simple recursive implementation for
// counting ways to reach a score using 1 and 2 with
// consecutive 2 allowed
function CountWays(n, flag)
{
// base cases
if (n == 0) {
return 1;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 1 + 1;
}
// For cases n > 2
return CountWays(n - 1) + CountWays(n - 3);
}
// Driver code
let n = 5;
document.write(CountWays(n, false));
</script>
Producción:
6
Podemos almacenar valores intermedios y resolverlos en O(n) tiempo y O(n) espacio.
C++
// Bottom up approach for
// counting ways to reach a score using 1 and 2 with
// consecutive 2 allowed
#include <iostream>
using namespace std;
int CountWays(int n)
{
// noOfWays[i] will store count for value i.
// 3 extra values are to take care of corner case n = 0
int noOfWays[n + 3];
noOfWays[0] = 1;
noOfWays[1] = 1;
noOfWays[2] = 1 + 1;
// Loop till "n+1" to compute value for "n"
for (int i=3; i<n+1; i++) {
noOfWays[i] =
// number of ways if first run is 1
noOfWays[i-1]
// number of ways if first run is 2
// and second run is 1
+ noOfWays[i-3];
}
return noOfWays[n];
}
int main()
{
int n = 0;
cout << CountWays(n);
return 0;
}
Java
import java.util.Arrays;
// Bottom up approach for
// counting ways to reach a score using
// 1 and 2 with consecutive 2 allowed
class GfG {
static int CountWays(int n)
{
// noOfWays[i] will store count for value i.
// 3 extra values are to take care of cornser case n
// = 0
int noOfWays[] = new int[n + 3];
noOfWays[0] = 1;
noOfWays[1] = 1;
noOfWays[2] = 1 + 1;
// Loop till "n+1" to compute value for "n"
for (int i = 3; i < n + 1; i++) {
noOfWays[i] =
// number of ways if first run is 1
noOfWays[i - 1]
// number of ways if first run is 2
// and second run is 1
+ noOfWays[i - 3];
}
return noOfWays[n];
}
public static void main(String[] args)
{
int n = 5;
System.out.println(CountWays(n));
}
}
Python3
# Bottom up approach for # counting ways to reach a score using # 1 and 2 with consecutive 2 allowed def CountWays(n): # noOfWays[i] will store count for value i. # 3 extra values are to take care of corner case n = 0 noOfWays = [0] * (n + 3) noOfWays[0] = 1 noOfWays[1] = 1 noOfWays[2] = 1 + 1 # Loop till "n+1" to compute value for "n" for i in range(3, n+1): # number of ways if first run is 1 # + # number of ways if first run is 2 # and second run is 1 noOfWays[i] = noOfWays[i-1] + noOfWays[i-3] return noOfWays[n] # Driver Code if __name__ == '__main__': n = 5 print(CountWays(n))
C#
// Bottom up approach for
// counting ways to reach a score using
// 1 and 2 with consecutive 2 allowed
using System;
class GfG
{
static int CountWays(int n)
{
// if this state is already visited return
// its value
if (dp[n, flag] != -1)
{
return dp[n, flag];
}
// base case
if (n == 0)
{
return 1;
}
// 2 is not scored last time so we can
// score either 2 or 1
int sum = 0;
if (flag == 0 && n > 1)
{
sum = sum + CountWays(n - 1, 0) +
CountWays(n - 2, 1);
}
// 2 is scored last time so we can only score 1
else
{
sum = sum + CountWays(n - 1, 0);
}
return dp[n,flag] = sum;
}
// Driver code
public static void Main(String[] args)
{
int n = 5;
for (int i = 0; i <dp.GetLength(0); i++)
for (int j = 0; j < dp.GetLength(1); j++)
dp[i,j]=-1;
Console.WriteLine(CountWays(n, 0));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Bottom up approach for
// counting ways to reach a score using
// 1 and 2 with consecutive 2 allowed
function CountWays(n)
{
// noOfWays[i] will store count for value i.
// 3 extra values are to take care of cornser case n
// = 0
var noOfWays = Array(n + 3).fill(0);
noOfWays[0] = 1;
noOfWays[1] = 1;
noOfWays[2] = 1 + 1;
// Loop till "n+1" to compute value for "n"
for (var i = 3; i < n + 1; i++) {
// number of ways if first run is 1
// number of ways if first run is 2
// and second run is 1
noOfWays[i] = noOfWays[i - 1] + noOfWays[i - 3];
}
return noOfWays[n];
}
// Driver code
var n = 5;
document.write(CountWays(n));
// This code is contributed by gauravrajput1
</script>
Producción:
6
Esto se puede mejorar aún más a O (n) tiempo y espacio constante almacenando solo los últimos 3 valores.
C++
// Bottom up approach for
// counting ways to reach a score using 1 and 2 with
// consecutive 2 allowed
#include <iostream>
using namespace std;
int CountWays(int n)
{
// noOfWays[i] will store count
// for last 3 values before i.
int noOfWays[3];
noOfWays[0] = 1;
noOfWays[1] = 1;
noOfWays[2] = 1 + 1;
// Loop till "n+1" to compute value for "n"
for (int i=3; i<n+1; i++) {
noOfWays[i] =
// number of ways if first run is 1
noOfWays[3-1]
// number of ways if first run is 2
// and second run is 1
+ noOfWays[3-3];
// Remember last 3 values
noOfWays[0] = noOfWays[1];
noOfWays[1] = noOfWays[2];
noOfWays[2] = noOfWays[i];
}
return noOfWays[n];
}
int main()
{
int n = 5;
cout << CountWays(n);
return 0;
}
Java
// Bottom up approach for
// counting ways to reach a score using 1 and 2 with
// consecutive 2 allowed
import java.io.*;
class GFG
{
static int CountWays(int n)
{
// noOfWays[i] will store count
// for last 3 values before i.
int noOfWays[] = new int[n + 3];
noOfWays[0] = 1;
noOfWays[1] = 1;
noOfWays[2] = 1 + 1;
// Loop till "n+1" to compute value for "n"
for (int i=3; i<n+1; i++) {
noOfWays[i] =
// number of ways if first run is 1
noOfWays[3-1]
// number of ways if first run is 2
// and second run is 1
+ noOfWays[3-3];
// Remember last 3 values
noOfWays[0] = noOfWays[1];
noOfWays[1] = noOfWays[2];
noOfWays[2] = noOfWays[i];
}
return noOfWays[n];
}
// Driver code
public static void main (String[] args) {
int n = 5;
System.out.println(CountWays(n));
}
}
// This code is contributed by shivanisinghss2110
Python3
# Bottom up approach for # counting ways to reach a score using 1 and 2 with # consecutive 2 allowed def CountWays(n): # noOfWays[i] will store count # for last 3 values before i. noOfWays = [0] * (n+1) noOfWays[0] = 1 noOfWays[1] = 1 noOfWays[2] = 1 + 1 # Loop till "n+1" to compute value for "n" for i in range(3, n+1): # number of ways if first run is 1 # number of ways if first run is 2 # and second run is 1 noOfWays[i] = noOfWays[3-1] + noOfWays[3-3] # Remember last 3 values noOfWays[0] = noOfWays[1] noOfWays[1] = noOfWays[2] noOfWays[2] = noOfWays[i] return noOfWays[n] if __name__ == '__main__': n = 5 print(CountWays(n)) # this code is contributed by shivanisingh2110
C#
// Bottom up approach for
// counting ways to reach a score using 1 and 2 with
// consecutive 2 allowed
using System;
using System.Collections.Generic;
public class GFG {
static int CountWays(int n) {
// noOfWays[i] will store count
// for last 3 values before i.
int []noOfWays = new int[n + 3];
noOfWays[0] = 1;
noOfWays[1] = 1;
noOfWays[2] = 1 + 1;
// Loop till "n+1" to compute value for "n"
for (int i = 3; i < n + 1; i++) {
noOfWays[i] =
// number of ways if first run is 1
noOfWays[3 - 1]
// number of ways if first run is 2
// and second run is 1
+ noOfWays[3 - 3];
// Remember last 3 values
noOfWays[0] = noOfWays[1];
noOfWays[1] = noOfWays[2];
noOfWays[2] = noOfWays[i];
}
return noOfWays[n];
}
// Driver code
public static void Main(String[] args) {
int n = 5;
Console.WriteLine(CountWays(n));
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// Bottom up approach for
// counting ways to reach a score using 1 and 2 with
// consecutive 2 allowed
function CountWays(n)
{
// noOfWays[i] will store count
// for last 3 values before i.
var noOfWays = Array(3).fill(0);
noOfWays[0] = 1;
noOfWays[1] = 1;
noOfWays[2] = 1 + 1;
// Loop till "n+1" to compute value for "n"
for (var i = 3; i < n + 1; i++) {
noOfWays[i] =
// number of ways if first run is 1
noOfWays[3-1]
// number of ways if first run is 2
// and second run is 1
+ noOfWays[3-3];
// Remember last 3 values
noOfWays[0] = noOfWays[1];
noOfWays[1] = noOfWays[2];
noOfWays[2] = noOfWays[i];
}
return noOfWays[n];
}
var n = 5;
document.write(CountWays(n));
// This code is contributed by shivanisinghss2110
</script>
Producción
6
Publicación traducida automáticamente
Artículo escrito por Kushdeep_Mittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA