给定一个整数n，我们必须找到斯特恩双原子级数的第n项。 斯特恩双原子系 是生成以下整数序列0、1、1、2、1、3、2、3、1、4、3、5、2、5、3、4、……。它出现在 卡尔金威尔夫树 .有时也被称为 fusc 作用 在数学上，斯特恩双原子级数的序列P（n）由递推关系定义。 
例如：
null
Input : n = 7Output : 3Input : n = 15Output : 4
方法： 我们用一个非常简单的动态规划概念来解决这个问题 斐波那契数 保存DP[0]=0，DP[1]=1的基本情况后，我们必须简单地从i=2遍历到n，并根据Stern双原子级数的解释定义计算DP[i]。最后返回DP[n]的值。 算法：
// SET the Base case DP[0] = 0; DP[1] = 1; // Traversing the array from 2nd Element to nth Element for (int i=2; i<=n; i++) { // Case 1: for even n if (i%2 == 0) DP[i] = DP[i/2]; // Case 2: for odd n else DP[i] = DP[(i-1)/2] + DP[(i+1)/2]; } return DP[n];
C++
// Program to find the nth element // of Stern's Diatomic Series #include <bits/stdc++.h> using namespace std; // function to find nth stern' // diatomic series int findSDSFunc( int n) { // Initializing the DP array int DP[n+1]; // SET the Base case DP[0] = 0; DP[1] = 1; // Traversing the array from // 2nd Element to nth Element for ( int i = 2; i <= n; i++) { // Case 1: for even n if (i % 2 == 0) DP[i] = DP[i / 2]; // Case 2: for odd n else DP[i] = DP[(i - 1) / 2] + DP[(i + 1) / 2]; } return DP[n]; } // Driver program int main() { int n = 15; cout << findSDSFunc(n) << endl; return 0; } |
JAVA
// Java program to find the nth element // of Stern's Diatomic Series class GFG { // function to find nth stern' // diatomic series static int findSDSFunc( int n) { // Initializing the DP array int DP[] = new int [n+ 1 ]; // SET the Base case DP[ 0 ] = 0 ; DP[ 1 ] = 1 ; // Traversing the array from // 2nd Element to nth Element for ( int i = 2 ; i <= n; i++) { // Case 1: for even n if (i % 2 == 0 ) DP[i] = DP[i / 2 ]; // Case 2: for odd n else DP[i] = DP[(i - 1 ) / 2 ] + DP[(i + 1 ) / 2 ]; } return DP[n]; } // Driver program public static void main(String[] args) { int n = 15 ; System.out.println(findSDSFunc(n)); } } // This code is contributed by Smita Semwal. |
Python 3
# Program to find the nth element # of Stern's Diatomic Series # function to find nth stern' # diatomic series def findSDSFunc(n): # Initializing the DP array DP = [ 0 ] * (n + 1 ) # SET the Base case DP[ 0 ] = 0 DP[ 1 ] = 1 # Traversing the array from # 2nd Element to nth Element for i in range ( 2 , n + 1 ): # Case 1: for even n if ( int (i % 2 ) = = 0 ): DP[i] = DP[ int (i / 2 )] # Case 2: for odd n else : DP[i] = (DP[ int ((i - 1 ) / 2 )] + DP[ int ((i + 1 ) / 2 )]) return DP[n] # Driver program n = 15 print (findSDSFunc(n)) # This code is contribute by # Smitha Dinesh Semwal |
C#
// C# program to find the nth element // of Stern's Diatomic Series using System; class GFG { // function to find nth // stern' diatomic series static int findSDSFunc( int n) { // Initializing the DP array int []DP = new int [n + 1]; // SET the Base case DP[0] = 0; DP[1] = 1; // Traversing the array from // 2nd Element to nth Element for ( int i = 2; i <= n; i++) { // Case 1: for even n if (i % 2 == 0) DP[i] = DP[i / 2]; // Case 2: for odd n else DP[i] = DP[(i - 1) / 2] + DP[(i + 1) / 2]; } return DP[n]; } // Driver Code static public void Main () { int n = 15; Console.WriteLine(findSDSFunc(n)); } } // This code is contributed by aj_36 |
PHP
<?php // PHP Program to find the nth element // of Stern's Diatomic Series // function to find nth stern' // diatomic series function findSDSFunc( $n ) { // SET the Base case $DP [0] = 0; $DP [1] = 1; // Traversing the array from // 2nd Element to nth Element for ( $i = 2; $i <= $n ; $i ++) { // Case 1: for even n if ( $i % 2 == 0) $DP [ $i ] = $DP [ $i / 2]; // Case 2: for odd n else $DP [ $i ] = $DP [( $i - 1) / 2] + $DP [( $i + 1) / 2]; } return $DP [ $n ]; } // Driver Code $n = 15; echo (findSDSFunc( $n )); // This code is contributed by Ajit. ?> |
Javascript
<script> // JavaScript program to find the nth element // of Stern's Diatomic Series // function to find nth stern' // diatomic series function findSDSFunc(n) { // Initializing the DP array let DP = []; // SET the Base case DP[0] = 0; DP[1] = 1; // Traversing the array from // 2nd Element to nth Element for (let i = 2; i <= n; i++) { // Case 1: for even n if (i % 2 == 0) DP[i] = DP[i / 2]; // Case 2: for odd n else DP[i] = DP[(i - 1) / 2] + DP[(i + 1) / 2]; } return DP[n]; } // Driver code let n = 15; document.write(findSDSFunc(n)); // This code is contributed by souravghosh0416. </script> |
输出：
4
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
