第K个吊杆编号-yiteyi-C++库

吊杆编号仅由数字2和3组成。给定整数k（0 例如：

null

Input : k = 2Output: 3Input : k = 3Output: 22Input : k = 100Output: 322323Input: k = 1000000Output: 3332322223223222223

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

参考： http://www.spoj.com/problems/TSHOW1/ 这个想法很简单，就像生成二进制数 .这里我们也使用同样的方法，我们使用队列数据结构来解决这个问题。首先将“2”排到队列中，然后将“3”排到队列中。这两个分别是第一个和第二个动臂编号。现在设置count=2，每次pop（）在队列前面，并在poped number中添加“2”，如果（count==k），则增加count++，然后打印当前值臂数否则在poped number中添加“3”，并增加count++（count==k），然后打印当前值臂数 .重复这个过程直到到达K’th 臂数 . 这种方法可以被视为根为空字符串的树的BFS。每个节点的左子节点都附加了一个2，右子节点附加了3。

下面是这个想法的实施。

C++

                         // C++ program to find K'th Boom number                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         typedef                                     long                                     long                                     int                                     ll;                       
           
                         // This function uses queue data structure to K'th                       
                         // Boom number                       
                         void                                     boomNumber(ll k)                       
                         {                       
                                                 // Create an empty queue of strings                       
                                                 queue<string> q;                       
           
                                                 // Enqueue an empty string                       
                                                 q.push(                                     ""                                     );                       
           
                                                 // counter for K'th element                       
                                                 ll count = 0;                       
           
                                                 // This loop checks the value of count to                       
                                                 // become equal to K when value of count                       
                                                 // will be equals to k we will print the                       
                                                 // Boom number                       
                                                 while                                     (count <= k)                       
                                                 {                       
                                                 // current Boom number                       
                                                 string s1 = q.front();                       
           
                                                 // pop front                       
                                                 q.pop();                       
           
                                                 // Store current Boom number before changing it                       
                                                 string s2 = s1;                       
           
                                                 // Append "2" to string s1 and enqueue it                       
                                                 q.push(s1.append(                                     "2"                                     ));                       
                                                 count++;                       
           
                                                 // check if count==k                       
                                                 if                                     (count==k)                       
                                                 {                       
                                                 cout << s1 << endl;                                     // K'th Boom number                       
                                                 break                                     ;                       
                                                 }                       
           
                                                 // Append "3" to string s2 and enqueue it.                       
                                                 // Note that s2 contains the previous front                       
                                                 q.push(s2.append(                                     "3"                                     ));                       
                                                 count++;                       
           
                                                 // check if count==k                       
                                                 if                                     (count==k)                       
                                                 {                       
                                                 cout << s2 << endl;                                     // K'th Boom number                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                                 return                                     ;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 ll k = 1000000;                       
                                                 boomNumber(k);                       
                                                 return                                     0;                       
                         }                       

C#

                         // C# program to find K'th Boom number                       
                         using                                     System;                       
                         using                                     System.Collections;                       
           
                         class                                     GFG{                       
           
                         // This function uses queue data structure                       
                         // to K'th Boom number                       
                         static                                     void                                     boomNumber(                                     long                                     k)                       
                         {                       
                                   
                                                 // Create an empty queue of strings                       
                                                 Queue q =                                     new                                     Queue();                       
                                   
                                                 // Enqueue an empty string                       
                                                 q.Enqueue(                                     ""                                     );                       
                                   
                                                 // counter for K'th element                       
                                                 long                                     count = 0;                       
                                   
                                                 // This loop checks the value of count to                       
                                                 // become equal to K when value of count                       
                                                 // will be equals to k we will print the                       
                                                 // Boom number                       
                                                 while                                     (count <= k)                       
                                                 {                       
                                   
                                                 // current Boom number                       
                                                 string                                     s1 = (                                     string                                     )q.Dequeue();                       
                                   
                                                 // Store current Boom number                       
                                                 // before changing it                       
                                                 string                                     s2 = s1;                       
                                   
                                                 // Append "2" to string s1 and                       
                                                 // enqueue it                       
                                                 s1 +=                                     "2"                                     ;                       
                                                 q.Enqueue(s1);                       
                                                 count++;                       
                                   
                                                 // Check if count==k                       
                                                 if                                     (count == k)                       
                                                 {                       
                                   
                                                 // K'th Boom number                       
                                                 Console.Write(s1);                       
                                                 break                                     ;                       
                                                 }                       
                                   
                                                 // Append "3" to string s2 and enqueue it.                       
                                                 // Note that s2 contains the previous front                       
                                                 s2 +=                                     "3"                                     ;                       
                                                 q.Enqueue(s2);                       
                                                 count++;                       
                                   
                                                 // Check if count==k                       
                                                 if                                     (count == k)                       
                                                 {                       
                                   
                                                 // K'th Boom number                       
                                                 Console.Write(s2);                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                                 return                                     ;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main(                                     string                                     []arg)                       
                         {                       
                                                 long                                     k = 1000000;                       
                                   
                                                 boomNumber(k);                       
                         }                       
                         }                       
           
                         // This code is contributed by rutvik_56                       

输出：

3332322223223222223

本文由 沙申克·米什拉（古卢） .本文由Geeksforgeks团队审阅。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章