给定n位数,打印所有n位数,其奇偶位置的位数之和的绝对差为1。解决方案不应考虑引导0作为数字。 例如:
null
Input: n = 2Output: 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98Input: n = 3Output: 100 111 120 122 131 133 142 144 153 155 164 166 175 177 186 188 197 199 210 221 230 232 241 243 252 254 263 265 274 276 285 287 296 298 320 331 340 342 351 353 362 364 373 375 384 386 395 397 430 441 450 452 461 463 472 474 483 485 494 496 540 551 560 562 571 573 582 584 593 595 650 661 670 672 681 683 692 694 760 771 780 782 791 793 870 881 890 892 980 991
其思想是使用递归生成所有n位数字,并在两个单独的变量中保持迄今为止的偶数和奇数之和。对于一个给定的位置,我们用0到9之间的所有数字填充它,根据当前位置是偶数还是奇数,我们增加偶数或奇数和。我们单独处理前导0的情况,因为它们不算作数字。 我们遵循了从零开始的编号,比如数组索引。i、 e.前导(最左边的)数字被视为在偶数位置出现,相邻的数字被视为在奇数位置出现,以此类推。 以下是上述理念的实施——
C++
// A C++ recursive program to print all N-digit numbers with // absolute difference between sum of even and odd digits is 1 #include <bits/stdc++.h> using namespace std; // Recursive function to print all N-digit numbers with absolute // difference between sum of even and odd digits is 1. // This function considers leading zero as a digit // n --> value of input // out --> output array // index --> index of next digit to be filled in output array // evenSum, oddSum --> sum of even and odd digits so far void findNDigitNumsUtil( int n, char * out, int index, int evenSum, int oddSum) { // Base case if (index > n) return ; // If number becomes n-digit if (index == n) { // if absolute difference between sum of even and // odd digits is 1, print the number if ( abs (evenSum - oddSum) == 1) { out[index] = ' ' ; cout << out; } return ; } // If current index is odd, then add it to odd sum and recurse if (index & 1) { for ( int i = 0; i <= 9; i++) { out[index] = i + '0' ; findNDigitNumsUtil(n, out, index + 1, evenSum, oddSum + i); } } else // else add to even sum and recurse { for ( int i = 0; i <= 9; i++) { out[index] = i + '0' ; findNDigitNumsUtil(n, out, index + 1, evenSum + i, oddSum); } } } // This is mainly a wrapper over findNDigitNumsUtil. // It explicitly handles leading digit and calls // findNDigitNumsUtil() for remaining indexes. int findNDigitNums( int n) { // output array to store n-digit numbers char out[n + 1]; // Initialize number index considered so far int index = 0; // Initialize even and odd sums int evenSum = 0, oddSum = 0; // Explicitly handle first digit and call recursive function // findNDigitNumsUtil for remaining indexes. Note that the // first digit is considered to be present in even position. for ( int i = 1; i <= 9; i++) { out[index] = i + '0' ; findNDigitNumsUtil(n, out, index + 1, evenSum + i, oddSum); } } // Driver program int main() { int n = 3; findNDigitNums(n); return 0; } |
JAVA
// Java program to print all n-digit numbers // with absolute difference between sum // of even and odd digits is 1 import java.io.*; import java.util.*; class GFG { // Recursive function to print all N-digit numbers // with absolute difference between sum of even // and odd digits is 1. This function considers // leading zero as a digit // n --> value of input // out --> output array // index --> index of next digit to be filled in output array // evenSum, oddSum --> sum of even and odd digits so far static void findNDigitNumsUtil( int n, char out[], int index, int evenSum, int oddSum) { // Base case if (index > n) return ; // If number becomes n-digit if (index == n) { // if absolute difference between sum of even and // odd digits is 1, print the number if (Math.abs(evenSum - oddSum) == 1 ) { out[index] = ' ' ; System.out.print(out); } return ; } // If current index is odd, then add it to odd sum and recurse if (index % 2 != 0 ) { for ( int i = 0 ; i <= 9 ; i++) { out[index] = ( char )(i + '0' ); findNDigitNumsUtil(n, out, index + 1 , evenSum, oddSum + i); } } else // else add to even sum and recurse { for ( int i = 0 ; i <= 9 ; i++) { out[index] = ( char )(i + '0' ); findNDigitNumsUtil(n, out, index + 1 , evenSum + i, oddSum); } } } // This is mainly a wrapper over findNDigitNumsUtil. // It explicitly handles leading digit and calls // findNDigitNumsUtil() for remaining indexes static void findNDigitNums( int n) { // output array to store n-digit numbers char [] out = new char [n + 1 ]; // Initialize number index considered so far int index = 0 ; // Initialize even and odd sums int evenSum = 0 , oddSum = 0 ; // Explicitly handle first digit and call recursive function // findNDigitNumsUtil for remaining indexes. Note that the // first digit is considered to be present in even position for ( int i = 1 ; i <= 9 ; i++) { out[index] = ( char )(i + '0' ); findNDigitNumsUtil(n, out, index + 1 , evenSum + i, oddSum); } } // Driver program public static void main (String[] args) { int n = 3 ; findNDigitNums(n); } } // This code is contributed by Pramod Kumar |
Python 3
# Python 3 recursive program to print all N-digit # numbers with absolute difference between sum of # even and odd digits is 1 # Recursive function to print all N-digit numbers # with absolute difference between sum of even and # odd digits is 1. This function considers leading # zero as a digit # n --> value of input # out --> output array # index --> index of next digit to be filled # in output array # evenSum, oddSum --> sum of even and odd # digits so far def findNDigitNumsUtil(n, out, index, evenSum, oddSum): # Base case if (index > n): return # If number becomes n-digit if (index = = n): # if absolute difference between sum of even # and odd digits is 1, print the number if ( abs (evenSum - oddSum) = = 1 ): out[index] = '' out = ''.join(out) print (out, end = " " ) return # If current index is odd, then add it # to odd sum and recurse if (index & 1 ): for i in range ( 10 ): out[index] = chr (i + ord ( '0' )) findNDigitNumsUtil(n, out, index + 1 , evenSum, oddSum + i) else : # else add to even sum and recurse for i in range ( 10 ): out[index] = chr (i + ord ( '0' )) findNDigitNumsUtil(n, out, index + 1 , evenSum + i, oddSum) # This is mainly a wrapper over findNDigitNumsUtil. # It explicitly handles leading digit and calls # findNDigitNumsUtil() for remaining indexes. def findNDigitNums(n): # output array to store n-digit numbers out = [ 0 ] * (n + 1 ) # Initialize number index considered # so far index = 0 # Initialize even and odd sums evenSum = 0 oddSum = 0 # Explicitly handle first digit and call # recursive function findNDigitNumsUtil # for remaining indexes. Note that the # first digit is considered to be present # in even position. for i in range ( 1 , 10 ): out[index] = chr (i + ord ( '0' )) findNDigitNumsUtil(n, out, index + 1 , evenSum + i, oddSum) # Driver Code if __name__ = = "__main__" : n = 3 findNDigitNums(n) # This code is contributed by ita_c |
C#
// C# program to print all n-digit numbers // with absolute difference between sum // of even and odd digits is 1 using System; class GFG { // Recursive function to print all N-digit // numbers with absolute difference between // sum of even and odd digits is 1. This // function considers leading zero as a // digit // n --> value of input // out --> output array // index --> index of next digit to be // filled in output array // evenSum, oddSum --> sum of even and // odd digits so far static void findNDigitNumsUtil( int n, char []ou, int index, int evenSum, int oddSum) { // Base case if (index > n) return ; // If number becomes n-digit if (index == n) { // if absolute difference between sum // of even and odd digits is 1, print // the number if (Math.Abs(evenSum - oddSum) == 1) { ou[index] = ' ' ; Console.Write(ou); Console.Write( " " ); } return ; } // If current index is odd, then add it // to odd sum and recurse if (index % 2 != 0) { for ( int i = 0; i <= 9; i++) { ou[index] = ( char )(i + '0' ); findNDigitNumsUtil(n, ou, index + 1, evenSum, oddSum + i); } } else // else add to even sum and recurse { for ( int i = 0; i <= 9; i++) { ou[index] = ( char )(i + '0' ); findNDigitNumsUtil(n, ou, index + 1, evenSum + i, oddSum); } } } // This is mainly a wrapper over findNDigitNumsUtil. // It explicitly handles leading digit and calls // findNDigitNumsUtil() for remaining indexes static void findNDigitNums( int n) { // output array to store n-digit numbers char []ou = new char [n + 1]; // Initialize number index considered so far int index = 0; // Initialize even and odd sums int evenSum = 0, oddSum = 0; // Explicitly handle first digit and call // recursive function findNDigitNumsUtil for // remaining indexes. Note that the first // digit is considered to be present in even // position for ( int i = 1; i <= 9; i++) { ou[index] = ( char )(i + '0' ); findNDigitNumsUtil(n, ou, index + 1, evenSum + i, oddSum); } } // Driver program public static void Main () { int n = 3; findNDigitNums(n); } } // This code is contributed by nitin mittal. |
PHP
<?php // A PHP recursive program to print // all N-digit numbers with absolute // difference between sum of even // and odd digits is 1 // Recursive function to print all // N-digit numbers with absolute // difference between sum of even // and odd digits is 1. This function // considers leading zero as a digit // n --> value of input // out --> output array // index --> index of next digit // to be filled in output array // evenSum, oddSum --> sum of even // and odd digits so far function findNDigitNumsUtil( $n , $out , $index , $evenSum , $oddSum ) { // Base case if ( $index > $n ) return ; // If number becomes n-digit if ( $index == $n ) { // if absolute difference between sum of even and // odd digits is 1, print the number if ( abs ( $evenSum - $oddSum ) == 1) { echo implode( "" , $out ). " " ; } return ; } // If current index is odd, then // add it to odd sum and recurse if ( $index & 1) { for ( $i = 0; $i <= 9; $i ++) { $out [ $index ] = $i + '0' ; findNDigitNumsUtil( $n , $out , $index + 1, $evenSum , $oddSum + $i ); } } else // else add to even sum and recurse { for ( $i = 0; $i <= 9; $i ++) { $out [ $index ] = $i + '0' ; findNDigitNumsUtil( $n , $out , $index + 1, $evenSum + $i , $oddSum ); } } } // This is mainly a wrapper over findNDigitNumsUtil. // It explicitly handles leading digit and calls // findNDigitNumsUtil() for remaining indexes. function findNDigitNums( $n ) { // output array to store n-digit numbers $out = array_fill (0, $n + 1, "" ); // Initialize number index considered so far $index = 0; // Initialize even and odd sums $evenSum = 0; $oddSum = 0; // Explicitly handle first digit and // call recursive function findNDigitNumsUtil // for remaining indexes. Note that the // first digit is considered to be present in even position. for ( $i = 1; $i <= 9; $i ++) { $out [ $index ] = $i + '0' ; findNDigitNumsUtil( $n , $out , $index + 1, $evenSum + $i , $oddSum ); } } // Driver program $n = 3; findNDigitNums( $n ); // This code is contributed by chandan_jnu ?> |
Javascript
<script> // Javascript program to print all n-digit numbers // with absolute difference between sum // of even and odd digits is 1 // Recursive function to print all N-digit numbers // with absolute difference between sum of even // and odd digits is 1. This function considers // leading zero as a digit // n --> value of input // out --> output array // index --> index of next digit to be filled in output array // evenSum, oddSum --> sum of even and odd digits so far function findNDigitNumsUtil(n, out, index, evenSum, oddSum) { // Base case if (index > n) return ; // If number becomes n-digit if (index == n) { // if absolute difference between sum of even and // odd digits is 1, print the number if (Math.abs(evenSum - oddSum) == 1) { out[index] = '' ; for (let i = 0; i < out.length; i++) { document.write(out[i]); } document.write( " " ); } return ; } // If current index is odd, then add it to odd sum and recurse if (index % 2 != 0) { for (let i = 0; i <= 9; i++) { out[index] = String.fromCharCode(i + '0' .charCodeAt(0)); findNDigitNumsUtil(n, out, index + 1, evenSum, oddSum + i); } } else // else add to even sum and recurse { for (let i = 0; i <= 9; i++) { out[index] = String.fromCharCode(i + '0' .charCodeAt(0)); findNDigitNumsUtil(n, out, index + 1, evenSum + i, oddSum); } } } // This is mainly a wrapper over findNDigitNumsUtil. // It explicitly handles leading digit and calls // findNDigitNumsUtil() for remaining indexes function findNDigitNums(n) { let out = new Array(n+1); for (let i=0;i<n+1;i++) { out[i]=0; } // Initialize number index considered so far let index = 0; // Initialize even and odd sums let evenSum = 0, oddSum = 0; // Explicitly handle first digit and call recursive function // findNDigitNumsUtil for remaining indexes. Note that the // first digit is considered to be present in even position for (let i = 1; i <= 9; i++) { out[index] = String.fromCharCode(i + '0' .charCodeAt(0)); findNDigitNumsUtil(n, out, index + 1, evenSum + i, oddSum); } } // Driver program let n = 3; findNDigitNums(n); // This code is contributed by avanitrachhadiya2155 </script> |
输出:
100 111 120 122 131 133 142 144 153 155 164 166 175 177 186 188 197 199 210 221 230 232 241 243 252 254 263 265 274 276 285 287 296 298 320 331 340 342 351 353 362 364 373 375 384 386 395 397 430 441 450 452 461 463 472 474 483 485 494 496 540 551 560 562 571 573 582 584 593 595 650 661 670 672 681 683 692 694 760 771 780 782 791 793 870 881 890 892 980 991
我们可以避免使用两个变量evenSum和oddSum。相反,我们可以维护单变量diff,它存储偶数和奇数之和之间的差。可以看到实现 在这里 . 本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek,并想贡献自己的力量,你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上,并帮助其他极客。 如果您发现任何不正确的地方,或者您想分享有关上述主题的更多信息,请写下评论。
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END