头脑风暴时间~一道比较有意思的算法题
给你这么个数列
112123123412345123456123456712345678123456789123456789101234567891011...
看出规律了吗 这个数列是由下列数列串合而成：
1
12
123
1234
12345
123456
1234567
12345678
123456789
12345678910
1234567891011
12345678910...
...

现在问题是给定1<=i<=2147483647
要求此数列的第i位

头脑风暴时间！！！


[解决办法]
额，很简单啊：
先来分析下这个序列，对于第K数列串，其值为：123……k，数字个数为k
对于第k+1个数列串，其值为：123……k(k+1),数字个数为k+1

前k个数列串总的数字个数为1+2+3+……+K = (1+k)*k/2
第k+1个数列串总的数字个数为(k+2)*(k+1)/2
因为第i个数必定在否一个数列串中，所以对于i，可以找到合适的k使得(1+k)*k/2 <= i <(k+2)*(k+1)/2
如果i = (1+k)*k/2,则i为第k个数列串的最后一个数，即 第i位 = k。
否则 i 在第 k+1 的数列串中，令m = i - (1+k)*k/2，则 第i位 = m。
例如：当i = 11，则k = 4，m = 11 - 10 = 1，则 第i位为 1。

至于求解合适的k，使得(1+k)*k/2 <= i <(k+2)*(k+1)/2，可以用解方程的方法，这样效率还是挺高的。
[解决办法]
楼上的办法很好……

【程序】

C/C++ code

#include <stdio.h>#include <math.h>void fun(int n){    int i;    i=(int)sqrt(2*n)-1;    while(1){        if((1+i)*i/2<=n&&(2+i)*(i+1)/2>=n) break;        i++;    }    printf("%d",n-(1+i)*i/2);}int main(){    int i;    for(i=1;i<=200;i++) fun(i);    printf("\n");    return 0;}