用给定的位数和位数求最大数-yiteyi-C++库

如何求给定位和的最大数 s 和位数 D ? 例如：

null

Input  : s = 9, d = 2Output : 90Input  : s = 20, d = 3Output : 992

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 简单解决方案 是考虑所有m位数，并用数字和s保持最大数的跟踪。该解的时间复杂度的接近上界是O（10）。 ^M ). 有一个 贪婪的方法 来解决这个问题。其思想是从最左边到最右边（或从最高有效数字到最低有效数字）逐个填充所有数字。我们将剩余金额与9进行比较，如果剩余金额大于9，我们将9放在当前位置，否则我们将剩余金额放在当前位置。因为我们从左到右填充数字，所以我们把最高的数字放在左边，因此得到最大的数字。下图是上述方法的说明：

图片[1]-用给定的位数和位数求最大数-yiteyi-C++库

以下是上述方法的实施情况：

C++

                         // C++ program to find the largest number that can be                       
                         // formed from given sum of digits and number of digits.                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         // Prints the smalles possible number with digit sum 's'                       
                         // and 'm' number of digits.                       
                         void                                     findLargest(                                     int                                     m,                                     int                                     s)                       
                         {                       
                                                 // If sum of digits is 0, then a number is possible                       
                                                 // only if number of digits is 1.                       
                                                 if                                     (s == 0)                       
                                                 {                       
                                                 (m == 1)? cout <<                                     "Largest number is "                                     << 0                       
                                                 : cout <<                                     "Not possible"                                     ;                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Sum greater than the maximum possible sum.                       
                                                 if                                     (s > 9*m)                       
                                                 {                       
                                                 cout <<                                     "Not possible"                                     ;                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Create an array to store digits of result                       
                                                 int                                     res[m];                       
           
                                                 // Fill from most significant digit to least                       
                                                 // significant digit.                       
                                                 for                                     (                                     int                                     i=0; i<m; i++)                       
                                                 {                       
                                                 // Fill 9 first to make the number largest                       
                                                 if                                     (s >= 9)                       
                                                 {                       
                                                 res[i] = 9;                       
                                                 s -= 9;                       
                                                 }                       
           
                                                 // If remaining sum becomes less than 9, then                       
                                                 // fill the remaining sum                       
                                                 else                       
                                                 {                       
                                                 res[i] = s;                       
                                                 s = 0;                       
                                                 }                       
                                                 }                       
           
                                                 cout <<                                     "Largest number is "                                     ;                       
                                                 for                                     (                                     int                                     i=0; i<m; i++)                       
                                                 cout << res[i];                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     s = 9, m = 2;                       
                                                 findLargest(m, s);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find the largest number that can be                       
                         // formed from given sum of digits and number of digits                       
           
                         class                                     GFG                       
                         {                       
                                                 // Function to print the largest possible number with digit sum 's'                       
                                                 // and 'm' number of digits                       
                                                 static                                     void                                     findLargest(                                     int                                     m,                                     int                                     s)                       
                                                 {                       
                                                 // If sum of digits is 0, then a number is possible                       
                                                 // only if number of digits is 1                       
                                                 if                                     (s ==                                     0                                     )                       
                                                 {                       
                                                 System.out.print(m ==                                     1                                     ?                                     "Largest number is 0"                                     :                                     "Not possible"                                     );                       
                                   
                                                 return                                     ;                       
                                                 }                       
                                   
                                                 // Sum greater than the maximum possible sum                       
                                                 if                                     (s >                                     9                                     *m)                       
                                                 {                       
                                                 System.out.println(                                     "Not possible"                                     );                       
                                                 return                                     ;                       
                                                 }                       
                                   
                                                 // Create an array to store digits of result                       
                                                 int                                     [] res =                                     new                                     int                                     [m];                       
                                   
                                                 // Fill from most significant digit to least                       
                                                 // significant digit                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<m; i++)                       
                                                 {                       
                                                 // Fill 9 first to make the number largest                       
                                                 if                                     (s >=                                     9                                     )                       
                                                 {                       
                                                 res[i] =                                     9                                     ;                       
                                                 s -=                                     9                                     ;                       
                                                 }                       
                                   
                                                 // If remaining sum becomes less than 9, then                       
                                                 // fill the remaining sum                       
                                                 else                       
                                                 {                       
                                                 res[i] = s;                       
                                                 s =                                     0                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 System.out.print(                                     "Largest number is "                                     );                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<m; i++)                       
                                                 System.out.print(res[i]);                       
                                                 }                       
                                   
                                                 // driver program                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     s =                                     9                                     , m =                                     2                                     ;                       
                                                 findLargest(m, s);                       
                                                 }                       
                         }                       
           
                         // Contributed by Pramod Kumar                       

Python3

                         # Python 3 program to find                       
                         # the largest number that                       
                         # can be formed from given                       
                         # sum of digits and number                       
                         # of digits.                       
           
           
                         # Prints the smalles                       
                         # possible number with digit                       
                         # sum 's' and 'm' number of                       
                         # digits.                       
                         def                                     findLargest( m, s) :                       
           
                                                 # If sum of digits is 0,                       
                                                 # then a number is possible                       
                                                 # only if number of digits                       
                                                 # is 1.                       
                                                 if                                     (s                                     =                                     =                                     0                                     ) :                       
                                   
                                                 if                                     (m                                     =                                     =                                     1                                     ) :                       
                                                 print                                     (                                     "Largest number is "                                     ,                                     "0"                                     ,end                                     =                                     "")                       
                                                 else                                     :                       
                                                 print                                     (                                     "Not possible"                                     ,end                                     =                                     "")                       
                                   
                                                 return                       
           
                                                 # Sum greater than the                       
                                                 # maximum possible sum.                       
                                                 if                                     (s >                                     9                                     *                                     m) :                       
                                                 print                                     (                                     "Not possible"                                     ,end                                     =                                     "")                       
                                                 return                       
                                   
                                                 # Create an array to                       
                                                 # store digits of                       
                                                 # result                       
                                                 res                                     =                                     [                                     0                                     ]                                     *                                     m                       
           
                                                 # Fill from most significant                       
                                                 # digit to least significant                       
                                                 # digit.                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , m) :                       
                                   
                                                 # Fill 9 first to make                       
                                                 # the number largest                       
                                                 if                                     (s >                                     =                                     9                                     ) :                       
                                                 res[i]                                     =                                     9                       
                                                 s                                     =                                     s                                     -                                     9                       
                                   
                                                 # If remaining sum                       
                                                 # becomes less than                       
                                                 # 9, then fill the                       
                                                 # remaining sum                       
                                                 else                                     :                       
                                                 res[i]                                     =                                     s                       
                                                 s                                     =                                     0                       
                                   
                                   
                                                 print                                     (                                     "Largest number is "                                     ,end                                     =                                     "")                       
                                   
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , m) :                       
                                                 print                                     (res[i],end                                     =                                     "")                       
           
                         # Driver code                       
                         s                                     =                                     9                       
                         m                                     =                                     2                       
                         findLargest(m, s)                       
           
                         # This code is contributed by Nikita Tiwari.                       

C#

                         // C# program to find the                       
                         // largest number that can                       
                         // be formed from given sum                       
                         // of digits and number of digits                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                                                 // Function to print the                       
                                                 // largest possible number                       
                                                 // with digit sum 's' and                       
                                                 // 'm' number of digits                       
                                                 static                                     void                                     findLargest(                                     int                                     m,                                     int                                     s)                       
                                                 {                       
                                                 // If sum of digits is 0,                       
                                                 // then a number is possible                       
                                                 // only if number of digits is 1                       
                                                 if                                     (s == 0)                       
                                                 {                       
                                                 Console.Write(m == 1 ?                       
                                                 "Largest number is 0"                                     :                       
                                                 "Not possible"                                     );                       
                                   
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Sum greater than the                       
                                                 // maximum possible sum                       
                                                 if                                     (s > 9 * m)                       
                                                 {                       
                                                 Console.WriteLine(                                     "Not possible"                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Create an array to                       
                                                 // store digits of result                       
                                                 int                                     []res =                                     new                                     int                                     [m];                       
           
                                                 // Fill from most significant                       
                                                 // digit to least significant digit                       
                                                 for                                     (                                     int                                     i = 0; i < m; i++)                       
                                                 {                       
                                                 // Fill 9 first to make                       
                                                 // the number largest                       
                                                 if                                     (s >= 9)                       
                                                 {                       
                                                 res[i] = 9;                       
                                                 s -= 9;                       
                                                 }                       
           
                                                 // If remaining sum becomes                       
                                                 // less than 9, then                       
                                                 // fill the remaining sum                       
                                                 else                       
                                                 {                       
                                                 res[i] = s;                       
                                                 s = 0;                       
                                                 }                       
                                                 }                       
           
                                                 Console.Write(                                     "Largest number is "                                     );                       
                                                 for                                     (                                     int                                     i = 0; i < m; i++)                       
                                                 Console.Write(res[i]);                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 static                                     public                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     s = 9, m = 2;                       
                                                 findLargest(m, s);                       
                                                 }                       
                         }                       
           
                         // This code is Contributed by ajit                       

PHP

                         <?php                       
                         // PHP program to find the largest                       
                         // number that can be formed from                       
                         // given sum of digits and number                       
                         // of digits.                       
           
                         // Prints the smalles possible                       
                         // number with digit sum 's'                       
                         // and 'm' number of digits.                       
                         function                                     findLargest(                                     $m                                     ,                                     $s                                     )                       
                         {                       
                                                 // If sum of digits is 0, then                       
                                                 // a number is possible only if                       
                                                 // number of digits is 1.                       
                                                 if                                     (                                     $s                                     == 0)                       
                                                 {                       
                                                 if                                     ((                                     $m                                     == 1) == true)                       
                                                 echo                                     "Largest number is "                                     , 0;                       
                                                 else                       
                                                 echo                                     "Not possible"                                     ;                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Sum greater than the                       
                                                 // maximum possible sum.                       
                                                 if                                     (                                     $s                                     > 9 *                                     $m                                     )                       
                                                 {                       
                                                 echo                                     "Not possible"                                     ;                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Create an array to store                       
                                                 // digits of result Fill from                       
                                                 // most significant digit to                       
                                                 // least significant digit.                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $m                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // Fill 9 first to make                       
                                                 // the number largest                       
                                                 if                                     (                                     $s                                     >= 9)                       
                                                 {                       
                                                 $res                                     [                                     $i                                     ] = 9;                       
                                                 $s                                     -= 9;                       
                                                 }                       
           
                                                 // If remaining sum becomes                       
                                                 // less than 9, then fill                       
                                                 // the remaining sum                       
                                                 else                       
                                                 {                       
                                                 $res                                     [                                     $i                                     ] =                                     $s                                     ;                       
                                                 $s                                     = 0;                       
                                                 }                       
                                                 }                       
           
                                                 echo                                     "Largest number is "                                     ;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $m                                     ;                                     $i                                     ++)                       
                                                 echo                                     $res                                     [                                     $i                                     ];                       
                         }                       
           
                         // Driver code                       
                         $s                                     = 9;                                     $m                                     = 2;                       
                         findLargest(                                     $m                                     ,                                     $s                                     );                       
           
                         // This code is contributed by m_kit                       
                         ?>                       

Javascript

                         <script>                       
                         // Javascript program to find the largest number that can be                       
                         // formed from given sum of digits and number of digits.                       
           
                         // Prints the smalles possible number with digit sum 's'                       
                         // and 'm' number of digits.                       
                         function                                     findLargest(m, s)                       
                         {                       
                                                 // If sum of digits is 0, then a number is possible                       
                                                 // only if number of digits is 1.                       
                                                 if                                     (s == 0)                       
                                                 {                       
                                                 (m == 1)? document.write(                                     "Largest number is "                                     + 0)                       
                                                 : document.write(                                     "Not possible"                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Sum greater than the maximum possible sum.                       
                                                 if                                     (s > 9*m)                       
                                                 {                       
                                                 document.write(                                     "Not possible"                                     );                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // Create an array to store digits of result                       
                                                 let res =                                     new                                     Array(m);                       
           
                                                 // Fill from most significant digit to least                       
                                                 // significant digit.                       
                                                 for                                     (let i=0; i<m; i++)                       
                                                 {                       
                                                 // Fill 9 first to make the number largest                       
                                                 if                                     (s >= 9)                       
                                                 {                       
                                                 res[i] = 9;                       
                                                 s -= 9;                       
                                                 }                       
           
                                                 // If remaining sum becomes less than 9, then                       
                                                 // fill the remaining sum                       
                                                 else                       
                                                 {                       
                                                 res[i] = s;                       
                                                 s = 0;                       
                                                 }                       
                                                 }                       
           
                                                 document.write(                                     "Largest number is "                                     );                       
                                                 for                                     (let i=0; i<m; i++)                       
                                                 document.write(res[i]);                       
                         }                       
           
                         // Driver code                       
                                                 let s = 9, m = 2;                       
                                                 findLargest(m, s);                       
           
                         // This code is contributed by Mayank Tyagi                       
           
                         </script>                       

输出：

Largest number is 90

该解的时间复杂度为O（m）。本文由 瓦伊巴夫·阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章