在序列1，1，2，1，2，3，1，2，3，4中找到第n项…。-yiteyi-C++库

考虑整数的无穷序列：1, 1, 2、1, 2, 3、1, 2, 3、4, 1, 2、3, 4, 5…序列是按以下方式建立的：首先写出数字1，然后写出从1到2的数字，然后写出从1到3的数字，然后写出从1到4的数字，依此类推。在序列的第n个位置找到数字。 例如：

null

Input : n = 3Output : 2The 3rd number in the sequence is 2.Input : 55Output : 10

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

第一种方法： 其思想是首先找到n的块数。要确定具有第n个数的块，我们首先从n中减去1（第一个块中的元素计数），然后减去2，然后减去3，依此类推，直到得到负n。减法的数量将是块的数量，块中的位置将是我们将得到的最后一个非负数。

C++

                         // CPP program to find the                       
                         // value at n-th place in                       
                         // the given sequence                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns n-th number in sequence                       
                         // 1, 1, 2, 1, 2, 3, 1, 2, 4, ...                       
                         int                                     findNumber(                                     int                                     n)                       
                         {                       
                                                 n--;                       
           
                                                 // One by one subtract counts                       
                                                 // elements in different blocks                       
                                                 int                                     i = 1;                       
                                                 while                                     (n >= 0)                       
                                                 {                       
                                                 n -= i;                       
                                                 ++i;                       
                                                 }                       
           
                                                 return                                     (n + i);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 3;                       
                                                 cout << findNumber(n) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find the                       
                         // value at n-th place in                       
                         // the given sequence                       
           
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
           
                                                 // Returns n-th number in sequence                       
                                                 // 1, 1, 2, 1, 2, 3, 1, 2, 4, ...                       
                                                 static                                     int                                     findNumber(                                     int                                     n)                       
                                                 {                       
                                                 n--;                       
           
                                                 // One by one subtract counts                       
                                                 // elements in different blocks                       
                                                 int                                     i =                                     1                                     ;                       
                                                 while                                     (n >=                                     0                                     )                       
                                                 {                       
                                                 n -= i;                       
                                                 ++i;                       
                                                 }                       
           
                                                 return                                     (n + i);                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     3                                     ;                       
                                   
                                                 System.out.println(findNumber(n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Ajit.                       

Python3

                         # Python code to find the value at                       
                         # n-th place in the given sequence                       
           
                         # Returns n-th number in sequence                       
                         # 1, 1, 2, 1, 2, 3, 1, 2, 4, ...                       
                         def                                     findNumber( n ):                       
                                   
                                                 n                                     -                                     =                                     1                       
                                   
                                                 # One by one subtract counts                       
                                                 # elements in different blocks                       
                                                 i                                     =                                     1                       
                                                 while                                     n >                                     =                                     0                                     :                       
                                                 n                                     -                                     =                                     i                       
                                                 i                                     +                                     =                                     1                       
                                                 return                                     (n                                     +                                     i)                       
           
                         # Driver code                       
                         n                                     =                                     3                       
                         print                                     (findNumber(n))                       
           
                         # This code is contributed                       
                         # by "Sharad_Bhardwaj".                       

C#

                         // C# program to find the                       
                         // value at n-th place in                       
                         // the given sequence                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                                                 // Returns n-th number in sequence                       
                                                 // 1, 1, 2, 1, 2, 3, 1, 2, 4, ...                       
                                                 static                                     int                                     findNumber(                                     int                                     n)                       
                                                 {                       
                                                 n--;                       
           
                                                 // One by one subtract counts                       
                                                 // elements in different blocks                       
                                                 int                                     i = 1;                       
                                                 while                                     (n >= 0)                       
                                                 {                       
                                                 n -= i;                       
                                                 ++i;                       
                                                 }                       
           
                                                 return                                     (n + i);                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 3;                       
                                                 Console.WriteLine(findNumber(n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to find the                       
                         // value at n-th place in                       
                         // the given sequence                       
           
           
                         // Returns n-th number in sequence                       
                         // 1, 1, 2, 1, 2, 3, 1, 2, 4, ...                       
                         function                                     findNumber(                                     $n                                     )                       
                         {                       
                                                 $n                                     --;                       
           
                                                 // One by one subtract counts                       
                                                 // elements in different blocks                       
                                                 $i                                     = 1;                       
                                                 while                                     (                                     $n                                     >= 0)                       
                                                 {                       
                                                 $n                                     -=                                     $i                                     ;                       
                                                 ++                                     $i                                     ;                       
                                                 }                       
           
                                                 return                                     (                                     $n                                     +                                     $i                                     );                       
                         }                       
           
                         // Driver code                       
                         $n                                     = 3;                       
                         echo                                     findNumber(                                     $n                                     );                       
           
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
                                                 // Javascript program to find the                       
                                                 // value at n-th place in                       
                                                 // the given sequence                       
                                   
                                                 // Returns n-th number in sequence                       
                                                 // 1, 1, 2, 1, 2, 3, 1, 2, 4, ...                       
                                                 function                                     findNumber(n)                       
                                                 {                       
                                                 n--;                       
           
                                                 // One by one subtract counts                       
                                                 // elements in different blocks                       
                                                 let i = 1;                       
                                                 while                                     (n >= 0)                       
                                                 {                       
                                                 n -= i;                       
                                                 ++i;                       
                                                 }                       
                                                 return                                     (n + i);                       
                                                 }                       
           
                         // Driver code                       
                                                 let n = 3;                       
                                                 document.write(findNumber(n));                       
                                   
                                                 // This code is contributed by mukesh07.                       
                         </script>                       

输出：

时间复杂性：O(√n） 第二种方法： 无限序列的答案可以在O（1）中完成。我们可以将顺序组织为：1（1）。这意味着第一个序列的位置是1，2（2）1，2，3（4）1，2，3，4（7）1，2，3，4，5（11），然后我们会有一个新的序列，更容易找到。1（1）2（2）4（3）7（4）11括号中的数字是新序列号之间的距离。为了找到这个数的基数，我们需要解方程n=x（x+1）/2+1[或x^2+x+2–2n=0]。我们需要隔离x（获得最大地板值）。然后我们使用在同一公式中得到的x，但现在结果将成为直线的基础。我们只需要计算作为输入的数字和作为基数的数字之间的距离。

n — base + 1

C++

                         // CPP program to find the                       
                         // value at n-th place in                       
                         // the given sequence                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Definition of findNumber                       
                         // function                       
                         int                                     findNumber(                                     int                                     n)                       
                         {                       
                                                 // Finding x from equation                       
                                                 // n = x(x + 1)/2 + 1                       
                                                 int                                     x = (                                     int                                     )                                     floor                                     ((-1 +                       
                                                 sqrt                                     (1 + 8 * n - 8)) / 2);                       
           
                                                 // Base of current block                       
                                                 int                                     base = (x * (x + 1)) / 2 + 1;                       
           
                                                 // Value of n-th element                       
                                                 return                                     n - base + 1;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 55;                       
                                                 cout << findNumber(n) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find the                       
                         // value at n-th place in                       
                         // the given sequence                       
           
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
           
                                                 // Definition of findNumber function                       
                                                 static                                     int                                     findNumber(                                     int                                     n)                       
                                                 {                       
                                   
                                                 // Finding x from equation                       
                                                 // n = x(x + 1)/2 + 1                       
                                                 int                                     x = (                                     int                                     )Math.floor((-                                     1                                     +                       
                                                 Math.sqrt(                                     1                                     +                                     8                                     * n -                                     8                                     )) /                                     2                                     );                       
           
                                                 // Base of current block                       
                                                 int                                     base = (x * (x +                                     1                                     )) /                                     2                                     +                                     1                                     ;                       
           
                                                 // Value of n-th element                       
                                                 return                                     n - base +                                     1                                     ;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     55                                     ;                       
                                   
                                                 System.out.println(findNumber(n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Ajit.                       

Python3

                         # Python program to find                       
                         # the value at n-th place                       
                         # in the given sequence                       
                         import                                     math                       
           
                         # Definition of findNumber function                       
                         def                                     findNumber( n ):                       
                                   
                                                 # Finding x from equation                       
                                                 # n = x(x + 1)/2 + 1                       
                                                 x                                     =                                     int                                     (math.floor((                                     -                                     1                                     +                                     math.sqrt(                                     1                       
                                                 +                                     8                                     *                                     n                                     -                                     8                                     ))                                     /                                     2                                     ))                       
           
                                                 # Base of current block                       
                                                 base                                     =                                     (x                                     *                                     (x                                     +                                     1                                     ))                                     /                                     2                                     +                                     1                       
                                   
                                                 # Value of n-th element                       
                                                 return                                     n                                     -                                     base                                     +                                     1                       
           
                         # Driver code                       
                         n                                     =                                     55                       
                         print                                     (findNumber(n))                       
           
                         # This code is contributed                       
                         # by "Abhishek Sharma 44"                       

C#

                         // C# program to find the                       
                         // value at n-th place in                       
                         // the given sequence                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                                                 // Definition of findNumber function                       
                                                 static                                     int                                     findNumber(                                     int                                     n)                       
                                                 {                       
           
                                                 // Finding x from equation                       
                                                 // n = x(x + 1)/2 + 1                       
                                                 int                                     x = (                                     int                                     )Math.Floor((-1 +                       
                                                 Math.Sqrt(1 + 8 * n - 8)) / 2);                       
           
                                                 // Base of current block                       
                                                 int                                     Base = (x * (x + 1)) / 2 + 1;                       
           
                                                 // Value of n-th element                       
                                                 return                                     n - Base + 1;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 55;                       
                                                 Console.WriteLine(findNumber(n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to find the                       
                         // value at n-th place in                       
                         // the given sequence                       
           
           
                         // Definition of findNumber function                       
                         function                                     findNumber(                                     $n                                     )                       
                         {                       
                                                 // Finding x from equation                       
                                                 // n = x(x + 1)/2 + 1                       
                                                 $x                                     =                                     floor                                     ((-1 + sqrt(1 +                       
                                                 8 *                                     $n                                     - 8)) / 2);                       
           
                                                 // Base of current block                       
                                                 $base                                     = (                                     $x                                     * (                                     $x                                     + 1)) / 2 + 1;                       
           
                                                 // Value of n-th element                       
                                                 return                                     $n                                     -                                     $base                                     + 1;                       
                         }                       
           
                         // Driver code                       
                         $n                                     = 55;                       
                         echo                                     findNumber(                                     $n                                     ) ;                       
           
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
                                                 // Javascript program to find the                       
                                                 // value at n-th place in                       
                                                 // the given sequence                       
                                   
                                                 // Definition of findNumber                       
                                                 // function                       
                                                 function                                     findNumber(n)                       
                                                 {                       
                                                 // Finding x from equation                       
                                                 // n = x(x + 1)/2 + 1                       
                                                 let x = Math.floor((-1 + Math.sqrt(1 + 8 * n - 8)) / 2);                       
           
                                                 // Base of current block                       
                                                 let base = (x * (x + 1)) / 2 + 1;                       
           
                                                 // Value of n-th element                       
                                                 return                                     n - base + 1;                       
                                                 }                       
                                   
                                                 let n = 55;                       
                                                 document.write(findNumber(n));                       
           
                         // This code is contributed by suresh07.                       
                         </script>                       

输出：

时间复杂性： O（1）本文由 萨加尔·舒克拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章