算法问题,把自然数1 2 3 4 5 6 7 8 9 10 11 12 13 14 15……排出来,去掉第2N个数,得1 3 5 7 9...
把自然数1 2 3 4 5 6 7 8 9 10 11 12 13 14 15……排出来,
N为不为0的自然数
去掉第2N个,得1 3 5 7 9 11 13 15 ……
去掉第3N个,得1 3 7 9 13 15 ……
去掉第4N个,得1 3 7 13 15……
去掉第5N个,得1 3 7 13 ……
……
问最终数列什么样子。
算法
[解决办法]
我们先从原始自然数来总结公式:
对于自然数1,2,3,4,5,6,...,
不去掉任何数的原始数列f(n) = n
去掉第2n个数后可以得到f(n) = 2n-1
去掉第3n个数后可以得到f(n) = [(3n-1)/2],'[]'表示取整
去掉第4n个数后可以得到f(n) = [(4n-1)/3]
去掉第kn个数后可以得到f(n) = [(kn-1)/(k-1)]
于是我们可以通过迭代计算出依次去掉第2N、3N、...、kN个数后的数列:
我们从去掉kN个数后开始向去掉第(k-1)N个数后迭代,假设去掉第kn个数后的的数列为f(k,n),那么我们可以得到f(k-1,n) = [((k-1)f(k,n)-1)/(k-2)],依次的我们就可以得到迭代到去掉第2N个数后的数列f(2,n) = 2f(3,n)-1。
例子:k = 3 的数列是?
f(3,1) = [(3-1)/2] =1, f(2,1) = 2f(3,1)-1 = 1
f(3,2) = [(6-1)/2] =2, f(2,2) = 2*2-1 = 3
f(3,3) = [(9-1)/2] =4, f(2,3) = 2*4-1 = 7
...
可以得到最终数列为:1,3,7,9,13,15,...
[解决办法]
数列长度10000,算到50N
1 3 7 13 19 27 39 49 63 79 91 109 133 147 181 207 223 253 289 307 349 387 399 459 481 529 567 613 649 709 763 807 843 927 949 1009 1093 1111 1189 1261 1321 1359 1471 1483 1579 1693 1719 1807 1899 1933 2019 2023 2029 2161 2163 2187 2263 2269 2311 2367 2439 2479 2527 2533 2559 2703 2707 2739 2779 2799 2851 2967 2979 3019 3073 3147 3159 3199 3207 3327 3373 3421 3447 3529 3553 3619 3691 3807 3819 3841 3883 3913 3987 4083 4123 4203 4239 4249 4347 4407 4429 4543 4603 4621 4623 4627 4681 4783 4843 4887 4891 4899 5067 5079 5149 5163 5173 5209 5293 5329 5401 5431 5539 5547 5563 5611 5667 5763 5767 5803 5893 5971 6013 6067 6109 6121 6159 6229 6283 6387 6399 6423 6559 6579 6589 6619 6723 6799 6859 6889 6927 6939 6991 7069 7189 7201 7219 7309 7321 7333 7369 7419 7483 7519 7579 7683 7741 7743 7839 7849 7921 7951 7963 7999 8029 8173 8283 8311 8367 8401 8403 8419 8461 8569 8593 8607 8743 8749 8787 8847 8907 8923 9039 9091 9151 9193 9279 9289 9303 9363 9423 9511 9547 9579 9643 9679 9723 9747 9829 9889 9913 9927