Dado un entero positivo n, la tarea es imprimir la secuencia de Gould hasta el término n.
En Matemáticas, la sucesión de Gould es una sucesión de enteros cuyo término n indica la cuenta de los números impares en la fila n-1 del triángulo pascal . Esta secuencia consiste solo en potencias de 2.
Por ejemplo :
Row Number Pascal's triangle count of odd numbers in ith row 0th row 1 1 1st row 1 1 2 2nd row 1 2 1 2 3rd row 1 3 3 1 4 4th row 1 4 6 4 1 2 5th row 1 5 10 10 5 1 4 6th row 1 6 15 20 15 6 1 4 7th row 1 7 21 35 35 21 7 1 8 8th row 1 8 28 56 70 56 28 8 1 2 9th row 1 9 36 84 126 126 84 36 9 1 4 10th row 1 10 45 120 210 256 210 120 45 10 1 4
Entonces, los primeros términos de la secuencia de Gould son:
1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32
Una solución simple para generar la secuencia de Gould es generar cada fila del triángulo de Pascal desde la fila 0 hasta la fila n y contar los números impares que aparecen en cada fila.
El iésimo elemento de la n-ésima fila se puede calcular fácilmente calculando el coeficiente binomial C(n, i).
Para obtener más detalles sobre este enfoque, consulte esto: el triángulo de Pascal .
A continuación se muestra la implementación de la idea anterior.
C++
// CPP program to generate
// Gould's Sequence
#include <bits/stdc++.h>
using namespace std;
// Function to generate gould's Sequence
void gouldSequence(int n)
{
// loop to generate each row
// of pascal's Triangle up to nth row
for (int row_num = 1; row_num <= n; row_num++) {
int count = 1;
int c = 1;
// Loop to generate each element of ith row
for (int i = 1; i <= row_num; i++) {
c = c * (row_num - i) / i;
// if c is odd
// increment count
if (c % 2 == 1)
count++;
}
// print count of odd elements
cout << count << " ";
}
}
// Driver code
int main()
{
// Get n
int n = 16;
// Function call
gouldSequence(n);
return 0;
}
Java
// JAVA program to generate
// Gould's Sequence
class GFG {
// Function to generate gould's Sequence
static void gouldSequence(int n)
{
// loop to generate each row
// of pascal's Triangle up to nth row
for (int row_num = 1; row_num <= n; row_num++) {
int count = 1;
int c = 1;
// Loop to generate each element of ith row
for (int i = 1; i <= row_num; i++) {
c = c * (row_num - i) / i;
// if c is odd
// increment count
if (c % 2 == 1)
count++;
}
// print count of odd elements
System.out.print(count + " ");
}
}
// Driver code
public static void main(String[] args)
{
// Get n
int n = 16;
// Function call
gouldSequence(n);
}
}
Python 3
# Python 3 program to generate # Gould's Sequence # Function to generate gould's Sequence def gouldSequence(n): # loop to generate each row # of pascal's Triangle up to nth row for row_num in range (1, n): count = 1 c = 1 # Loop to generate each # element of ith row for i in range (1, row_num): c = c * (row_num - i) / i # if c is odd # increment count if (c % 2 == 1): count += 1 # print count of odd elements print(count, end = " ") # Driver code # Get n n = 16; # Function call gouldSequence(n) # This code is contributed # by Akanksha Rai
C#
// C# program to generate
// Gould's Sequence
using System;
class GFG {
// Function to generate gould's Sequence
static void gouldSequence(int n)
{
// loop to generate each row
// of pascal's Triangle up to nth row
for (int row_num = 1; row_num <= n; row_num++) {
int count = 1;
int c = 1;
// Loop to generate each element of ith row
for (int i = 1; i <= row_num; i++) {
c = c * (row_num - i) / i;
// if c is odd
// increment count
if (c % 2 == 1)
count++;
}
// print count of odd elements
Console.Write(count + " ");
}
}
// Driver code
public static void Main()
{
// Get n
int n = 16;
// Function call
gouldSequence(n);
}
}
PHP
<?php
// PHP program to generate
// Gould's Sequence
// Function to generate gould's Sequence
function gouldSequence($n)
{
// loop to generate each row
// of pascal's Triangle up to nth row
for ($row_num = 1; $row_num <= $n; $row_num++) {
$count = 1;
$c = 1;
// Loop to generate each element of ith row
for ($i = 1; $i <= $row_num; $i++) {
$c = $c * ($row_num - $i) / $i;
// if c is odd
// increment count
if ($c % 2 == 1)
$count++;
}
// print count of odd elements
echo $count , " ";
}
}
// Driver code
// Get n
$n = 16;
// Function call
gouldSequence($n);
?>
Javascript
<script>
// Javascript program to generate
// Gould's Sequence
// Function to generate gould's Sequence
function gouldSequence(n)
{
// loop to generate each row
// of pascal's Triangle up to nth row
for (var row_num = 1; row_num <= n; row_num++) {
var count = 1;
var c = 1;
// Loop to generate each element of ith row
for (var i = 1; i <= row_num; i++) {
c = c * (row_num - i) / i;
// if c is odd
// increment count
if (c % 2 == 1)
count++;
}
// print count of odd elements
document.write( count + " ");
}
}
// Driver code
// Get n
var n = 16;
// Function call
gouldSequence(n);
</script>
Producción
1 2 2 4 2 4 4 8 2 4 4 8 4 8 8 16
Una Solución Eficiente se basa en el hecho de que la cuenta de números impares en la i-ésima fila del Triángulo de Pascal es 2 elevada a la cuenta de 1 en representación binaria de i.
Por ejemplo
for row=5 5 in binary = 101 count of 1's =2 22= 4 So, 5th row of pascal triangle will have 4 odd number
Al contar 1 en representación binaria de cada número de fila hasta n, podemos generar la Secuencia de Gould hasta n.
A continuación se muestra la implementación de la idea anterior.
C++
// CPP program to generate
// Gould's Sequence
#include <bits/stdc++.h>
using namespace std;
// Utility function to count odd numbers
// in ith row of Pascals's triangle
int countOddNumber(int row_num)
{
// Count set bits in row_num
// Initialize count as zero
unsigned int count = 0;
while (row_num) {
count += row_num & 1;
row_num >>= 1;
}
// Return 2^count
return (1 << count);
}
// Function to generate gould's Sequence
void gouldSequence(int n)
{
// loop to generate gould's Sequence up to n
for (int row_num = 0; row_num < n; row_num++) {
cout << countOddNumber(row_num) << " ";
}
}
// Driver code
int main()
{
// Get n
int n = 16;
// Function call
gouldSequence(n);
return 0;
}
Java
// JAVA program to generate
// Gould's Sequence
class GFG {
// Utility function to count odd numbers
// in ith row of Pascals's triangle
static int countOddNumber(int row_num)
{
// Count set bits in row_num
// Initialize count as zero
int count = 0;
while (row_num > 0) {
count += row_num & 1;
row_num >>= 1;
}
// Return 2^count
return (1 << count);
}
// Function to generate gould's Sequence
static void gouldSequence(int n)
{
// loop to generate gould's Sequence up to n
for (int row_num = 0; row_num < n; row_num++) {
System.out.print(countOddNumber(row_num) + " ");
}
}
// Driver code
public static void main(String[] args)
{
// Get n
int n = 16;
// Function call
gouldSequence(n);
}
}
Python3
# Python3 program to generate # Gould's Sequence # Utility function to count odd numbers # in ith row of Pascals's triangle def countOddNumber(row_num): # Count set bits in row_num # Initialize count as zero count = 0 while row_num != 0: count += row_num & 1 row_num >>= 1 # Return 2^count return (1 << count) # Function to generate gould's Sequence def gouldSequence(n): # loop to generate gould's # Sequence up to n for row_num in range(0, n): print(countOddNumber(row_num), end = " ") # Driver code if __name__ == "__main__": # Get n n = 16 # Function call gouldSequence(n) # This code is contributed # by Rituraj Jain
C#
// C# program to generate
// Gould's Sequence
using System;
class GFG {
// Utility function to count odd numbers
// in ith row of Pascals's triangle
static int countOddNumber(int row_num)
{
// Count set bits in row_num
// Initialize count as zero
int count = 0;
while (row_num > 0) {
count += row_num & 1;
row_num >>= 1;
}
// Return 2^count
return (1 << count);
}
// Function to generate gould's Sequence
static void gouldSequence(int n)
{
// loop to generate gould's Sequence up to n
for (int row_num = 0; row_num < n; row_num++) {
Console.Write(countOddNumber(row_num) + " ");
}
}
// Driver code
public static void Main()
{
// Get n
int n = 16;
// Function call
gouldSequence(n);
}
}
PHP
<?php
// PHP program to generate
// Gould's Sequence
// Utility function to count odd numbers
// in ith row of Pascals's triangle
function countOddNumber($row_num)
{
// Count set bits in row_num
// Initialize count as zero
$count = 0;
while ($row_num)
{
$count += $row_num & 1;
$row_num >>= 1;
}
// Return 2^count
return (1 << $count);
}
// Function to generate gould's Sequence
function gouldSequence($n)
{
// loop to generate gould's Sequence up to n
for ($row_num = 0;
$row_num < $n; $row_num++)
{
echo countOddNumber($row_num), " ";
}
}
// Driver code
// Get n
$n = 16;
// Function call
gouldSequence($n);
// This code is contributed
// by Sach_Code
?>
Javascript
<script>
// javascript program to generate
// Gould's Sequence
// Utility function to count odd numbers
// in ith row of Pascals's triangle
function countOddNumber(row_num)
{
// Count set bits in row_num
// Initialize count as zero
var count = 0;
while (row_num > 0) {
count += row_num & 1;
row_num >>= 1;
}
// Return 2^count
return (1 << count);
}
// Function to generate gould's Sequence
function gouldSequence(n)
{
// loop to generate gould's Sequence up to n
for (var row_num = 0; row_num < n; row_num++) {
document.write(countOddNumber(row_num) + " ");
}
}
// Driver code
// Get n
var n = 16;
// Function call
gouldSequence(n);
// This code is contributed by gauravrajput1
</script>
Producción
1 2 2 4 2 4 4 8 2 4 4 8 4 8 8 16
Una mejor solución (usando programación dinámica) se basa en la observación de que después de cada potencia de 2 términos anteriores se duplicaron.
Por ejemplo
first term of the sequence is - 1 Now After every power of 2 we will double the value of previous terms Terms up to 21 1 2 Terms up to 22 1 2 2 4 Terms up to 23 1 2 2 4 2 4 4 8 Terms up to 24 1 2 2 4 2 4 4 8 2 4 4 8 4 8 8 16
Entonces, podemos calcular los términos de la Secuencia de Gould después de 2 i duplicando el valor de los términos anteriores
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to generate
// Gould's Sequence
#include <bits/stdc++.h>
using namespace std;
// 32768 = 2^15
#define MAX 32768
// Array to store Sequence up to
// 2^16 = 65536
int arr[2 * MAX];
// Utility function to pre-compute odd numbers
// in ith row of Pascals's triangle
int gouldSequence()
{
// First term of the Sequence is 1
arr[0] = 1;
// Initialize i to 1
int i = 1;
// Initialize p to 1 (i.e 2^i)
// in each iteration
// i will be pth power of 2
int p = 1;
// loop to generate gould's Sequence
while (i <= MAX) {
// i is pth power of 2
// traverse the array
// from j=0 to i i.e (2^p)
int j = 0;
while (j < i) {
// double the value of arr[j]
// and store to arr[i+j]
arr[i + j] = 2 * arr[j];
j++;
}
// update i to next power of 2
i = (1 << p);
// increment p
p++;
}
}
// Function to print gould's Sequence
void printSequence(int n)
{
// loop to generate gould's Sequence up to n
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}
// Driver code
int main()
{
gouldSequence();
// Get n
int n = 16;
// Function call
printSequence(n);
return 0;
}
Java
// JAVA program to generate
// Gould's Sequence
class GFG {
// 32768 = 2^15
static final int MAX = 32768;
// Array to store Sequence up to
// 2^16 = 65536
static int[] arr = new int[2 * MAX];
// Utility function to pre-compute odd numbers
// in ith row of Pascals's triangle
static void gouldSequence()
{
// First term of the Sequence is 1
arr[0] = 1;
// Initialize i to 1
int i = 1;
// Initialize p to 1 (i.e 2^i)
// in each iteration
// i will be pth power of 2
int p = 1;
// loop to generate gould's Sequence
while (i <= MAX) {
// i is pth power of 2
// traverse the array
// from j=0 to i i.e (2^p)
int j = 0;
while (j < i) {
// double the value of arr[j]
// and store to arr[i+j]
arr[i + j] = 2 * arr[j];
j++;
}
// update i to next power of 2
i = (1 << p);
// increment p
p++;
}
}
// Function to print gould's Sequence
static void printSequence(int n)
{
// loop to generate gould's Sequence up to n
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
// Driver code
public static void main(String[] args)
{
gouldSequence();
// Get n
int n = 16;
// Function call
printSequence(n);
}
}
Python3
# Python3 program to generate # Gould's Sequence # 32768 = 2^15 MAX = 32768 # Array to store Sequence up to # 2^16 = 65536 arr = [None] * (2 * MAX) # Utility function to pre-compute # odd numbers in ith row of Pascals's # triangle def gouldSequence(): # First term of the Sequence is 1 arr[0] = 1 # Initialize i to 1 i = 1 # Initialize p to 1 (i.e 2^i) # in each iteration # i will be pth power of 2 p = 1 # loop to generate gould's Sequence while i <= MAX: # i is pth power of 2 # traverse the array # from j=0 to i i.e (2^p) j = 0 while j < i: # double the value of arr[j] # and store to arr[i+j] arr[i + j] = 2 * arr[j] j += 1 # update i to next power of 2 i = (1 << p) # increment p p += 1 # Function to print gould's Sequence def printSequence(n): # loop to generate gould's Sequence # up to n for i in range(0, n): print(arr[i], end = " ") # Driver code if __name__ == "__main__": gouldSequence() # Get n n = 16 # Function call printSequence(n) # This code is contributed # by Rituraj Jain
C#
// C# program to generate
// Gould's Sequence
using System;
class GFG {
// 32768 = 2^15
static int MAX = 32768;
// Array to store Sequence up to
// 2^16 = 65536
static int[] arr = new int[2 * MAX];
// Utility function to pre-compute odd numbers
// in ith row of Pascals's triangle
static void gouldSequence()
{
// First term of the Sequence is 1
arr[0] = 1;
// Initialize i to 1
int i = 1;
// Initialize p to 1 (i.e 2^i)
// in each iteration
// i will be pth power of 2
int p = 1;
// loop to generate gould's Sequence
while (i <= MAX) {
// i is pth power of 2
// traverse the array
// from j=0 to i i.e (2^p)
int j = 0;
while (j < i) {
// double the value of arr[j]
// and store to arr[i+j]
arr[i + j] = 2 * arr[j];
j++;
}
// update i to next power of 2
i = (1 << p);
// increment p
p++;
}
}
// Function to print gould's Sequence
static void printSequence(int n)
{
// loop to generate gould's Sequence up to n
for (int i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
}
// Driver code
public static void Main()
{
gouldSequence();
// Get n
int n = 16;
// Function call
printSequence(n);
}
}
PHP
<?php
// PHP program to generate
// Gould's Sequence
// 32768 = 2^15
$MAX = 32768;
// Array to store Sequence up to
// 2^16 = 65536
$arr = array_fill(0, 2 * $MAX, 0);
// Utility function to pre-compute
// odd numbers in ith row of
// Pascals's triangle
function gouldSequence()
{
global $MAX, $arr;
// First term of the Sequence is 1
$arr[0] = 1;
// Initialize i to 1
$i = 1;
// Initialize p to 1 (i.e 2^i)
// in each iteration
// i will be pth power of 2
$p = 1;
// loop to generate gould's Sequence
while ($i <= $MAX)
{
// i is pth power of 2
// traverse the array
// from j=0 to i i.e (2^p)
$j = 0;
while ($j < $i)
{
// double the value of arr[j]
// and store to arr[i+j]
$arr[$i + $j] = 2 * $arr[$j];
$j++;
}
// update i to next power of 2
$i = (1 << $p);
// increment p
$p++;
}
}
// Function to print gould's Sequence
function printSequence($n)
{
global $MAX, $arr;
// loop to generate gould's
// Sequence up to n
for ($i = 0; $i < $n; $i++)
{
echo $arr[$i]." ";
}
}
// Driver code
gouldSequence();
// Get n
$n = 16;
// Function call
printSequence($n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to generate
// Gould's Sequence
// 32768 = 2^15
var MAX = 32768;
// Array to store Sequence up to
// 2^16 = 65536
var arr = Array(2 * MAX);
// Utility function to pre-compute odd numbers
// in ith row of Pascals's triangle
function gouldSequence()
{
// First term of the Sequence is 1
arr[0] = 1;
// Initialize i to 1
var i = 1;
// Initialize p to 1 (i.e 2^i)
// in each iteration
// i will be pth power of 2
var p = 1;
// loop to generate gould's Sequence
while (i <= MAX) {
// i is pth power of 2
// traverse the array
// from j=0 to i i.e (2^p)
var j = 0;
while (j < i) {
// double the value of arr[j]
// and store to arr[i+j]
arr[i + j] = 2 * arr[j];
j++;
}
// update i to next power of 2
i = (1 << p);
// increment p
p++;
}
}
// Function to print gould's Sequence
function printSequence(n)
{
// loop to generate gould's Sequence up to n
for (var i = 0; i < n; i++) {
document.write( arr[i] + " ");
}
}
// Driver code
gouldSequence();
// Get n
var n = 16;
// Function call
printSequence(n);
</script>
Producción
1 2 2 4 2 4 4 8 2 4 4 8 4 8 8 16