![如何创建 2 个数字序列数组并将它们间歇性地连接在一起? (重击)](https://linux22.com/image/12259/%E5%A6%82%E4%BD%95%E5%88%9B%E5%BB%BA%202%20%E4%B8%AA%E6%95%B0%E5%AD%97%E5%BA%8F%E5%88%97%E6%95%B0%E7%BB%84%E5%B9%B6%E5%B0%86%E5%AE%83%E4%BB%AC%E9%97%B4%E6%AD%87%E6%80%A7%E5%9C%B0%E8%BF%9E%E6%8E%A5%E5%9C%A8%E4%B8%80%E8%B5%B7%EF%BC%9F%20%EF%BC%88%E9%87%8D%E5%87%BB%EF%BC%89.png)
我收到了这个挑战:
Examine the series of numbers shown below:
2 1 4 3 8 5 16 7 32 9 64 ...
2 is the 1st number in the series, 1 is the 2nd number in the series, etc.
Using Bash, create a program that finds the sum of the first 10,000 numbers.
Submit the first 10 digits of the sum as your answer.
(Answer: 2824934064)
我认为解决这个问题的方法是将系列分成 2 个,为每个序列创建一个 for 循环,并从我想要将它们合并在一起的位置创建一个新数组。
所以第一个序列会是这样的
1. 创建一个数组,从数字 2 开始,不断加倍,直到达到 10000 个数字。
第二个是
2. 创建一个数组,从数字 1 开始,不断添加 2,直到达到 10000 个数字。
然后是第三个数组,其中:
3. 我加入了 2 个数组,但它会类似于 {value1FromArray1, value1FromArray2, value2FromArray1, value2FromArray2...} 然后我希望在我总结的第三个数组中有 10000 个数字。
现在,我唯一想的是……我的方法听起来可以完成这项工作,但效率很低。我觉得有一个更简单的方法,与 for 循环或 while 循环有关。有什么建议么?我还没有尝试过任何东西。
答案1
不给出总和,但给你答案......
与乘法级数相比,加法级数很小,可以安全地忽略。忘了它。
如上所述,乘法仅涉及前 10 位数字。乘数是 2,所以结果的长度永远不会增加超过 1 位数字,我们只需要将结果保持在bash
数学的舒适范围内,同时保持足够长的长度以保持进位的准确性。
s=2; for ((i=1; i<=5000; i++)); do s=$((2*s)); s=${s:0:15}; done; echo ${s:0:10}
2824934064
仅仅因为 @rastafile 对几何级数中进位的处理让我大吃一惊,这里是另一个版本,我发现它更直观,尽管我承认这纯粹是抄袭
sum=2; carry=0; rgstr=
for ((i=1;i<=5000;i++)); do
#calculate from right to left over the string in sum
for (( j=${#sum}-1; j>=0; j-- )); do
#get the digit
x=${sum:$j:1}
#double the digit and add the current carry
x=$((x * 2 + carry))
#get the new carry
carry=$((${#x}-1))
#compose the intermediate string
#carry naturally indexes to the rightmost digit in x
rgstr=${x:$carry:1}$rgstr
done
#deal with any remaining carry before going round again
if [ $carry -eq 1 ]; then rgstr=$carry$rgstr; carry=0; fi
#load the sum from the register and then zero it
sum=$rgstr
rgstr=
(( $i % 100 == 0 )) && echo "$i iterations, sum is ${#sum} digits long"
done
echo "First ten digits of sum are ${sum:0:10}"
答案2
在 shell 中执行的一行命令(/bin/sh 或 /bin/bash):
A=2;B=1;S=0;i=1;while [ $i -le 60 ];do S=$(($S+$A+$B));A=$(($A*2));B=$(($B+2));i=$(($i+1));done;while [ $i -le 5000 ];do S=$(($S+$A));A=$(($A*2));A=${A:0:14};S=${S:0:14};i=$(($i+1));done;echo "${S:0:10}"
结果:
2824934064
解释:
# Initial variables
# A for array 1 member,
# B for array 2 member,
# S for sum we are looking for
# i to count number of iterations from 1 to 5000
A=2;B=1;S=0;i=1;
# For the first 60 arrays members, shell still can handle numbers,
# also second array influences the end result,
# so lets count result for 60 members separately
while [ $i -le 60 ] ; do
S=$(($S+$A+$B));
A=$(($A*2));
B=$(($B+2));
i=$(($i+1));
done;
# now result is about 19 symbols long,
# so, array 2 members which are 3 digit numbers
# do not influence the end result at all anymore,
# so we forget about array 2.
# also we restrict length of sum and members of array 1
# to less symbols.. I just take first 14 symbols each time
while [ $i -le 5000 ]; do
S=$(($S+$A));
A=$(($A*2));
A=${A:0:14};
S=${S:0:14};
i=$(($i+1));
done;
# print first 10 symbols of result
echo "${S:0:10}"
实际上结果符合预期;-)
答案3
1 2
2 4
3 8
4 16
5 32
6 64
7 128
8 256
9 512
10 1024
11 2048
12 4096
...
32 4294967296
...
48 281474976710656
...
64 18446744073709551616
...
1000 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
2000 114813069527425452423283320117768198402231770208869520047764273682576626139237031385665948631650626991844596463898746277344711896086305533142593135616665318539129989145312280000688779148240044871428926990063486244781615463646388363947317026040466353970904996558162398808944629605623311649536164221970332681344168908984458505602379484807914058900934776500429002716706625830522008132236281291761267883317206598995396418127021779858404042159853183251540889433902091920554957783589672039160081957216630582755380425583726015528348786419432054508915275783882625175435528800822842770817965453762184851149029376
3000 1230231922161117176931558813276752514640713895736833715766118029160058800614672948775360067838593459582429649254051804908512884180898236823585082482065348331234959350355845017413023320111360666922624728239756880416434478315693675013413090757208690376793296658810662941824493488451726505303712916005346747908623702673480919353936813105736620402352744776903840477883651100322409301983488363802930540482487909763484098253940728685132044408863734754271212592471778643949486688511721051561970432780747454823776808464180697103083861812184348565522740195796682622205511845512080552010310050255801589349645928001133745474220715013683413907542779063759833876101354235184245096670042160720629411581502371248008430447184842098610320580417992206662247328722122088513643683907670360209162653670641130936997002170500675501374723998766005827579300723253474890612250135171889174899079911291512399773872178519018229989376
...
END: 282493406427885207367041933403229466733779235036908223362737617171423633968541502511617825263342305274671206416862732165528407676139958676671942371453279846862103555703730798023755999290263414138746996425262647505106222430745688071901801071909721466836906811151133473603131174810929399280998101699398944715801811235142753236456432868426363041983113354252997303564408348123661878478353722682766588036480451677385451192294010288486562150551258990678187626397933471267212659382047684908251671777313746267962574481960017676147336443608528865821788061578040438881156396976534679536477744559804314840614495141020847691737745193471783611637455592871506037036173282712025702605093453646018500436656036503814680490899726366531275975724397022092725970923899174562238279814456008771885761907917633109135250592173833771549657868899882724833177350653880665122207329113965244413668948439622163744809859006963982753480759651997582823759605435167770997150230598943486938482234140460796206757230465587420581985312889685791023660711466304041608315840180083623903760913411030936698892365463484655371978555215241419051756637532976736697930030949995728239530882866713856024688223531470672787115758429874008695136417331917435528118587185775028585687114094178329752966233231383772407625995111380343784339467510448938064950157595661802643159880254674421388754566879844560548121596469573480869786916240396682202067625013440093219782321400568004201960905928079577408670605238675195724104384560742962264328294373028338181834383818752
前 10 位数字与 OP 中的相同。
1 必须从这个数字中2^5001
减去 2,然后加上其他系列,1+3+5+7...(见下文)
据我了解,挑战在于获得精确的结果。前十位数字只是快速检查,而不是解决方案。
这是 bash 脚本。大约需要 60 秒。我把它挤了一下,这样就合身了。
# reads $n from right to left and doubles each digit, with carry
doubn () {
carry=0; newn=''
for (( pos = ${#n} - 1; pos >= 0; pos-- ))
do
d=${n:pos:1}
dd=$(( 2 * d ))
if (( ${#dd} > 1 ))
# only take second digit, but keep new carry
then newd=${dd:1:1}; newcar=1
else newd=$dd; newcar=0
fi
# add (old) carry and save the new; $newd is max 8!
(( carry )) && (( newd++ ))
carry=$newcar
# build the new (doubled) string
newn="$newd$newn"
done
# add last carry, avoid leading zero
(( carry )) && n="$carry$newn" || n=$newn
}
n='1'
for (( cnt=1; cnt <= 5001; cnt++ ))
do
doubn
# print selected steps
(( cnt <= 64 || cnt % 1000 == 0 )) && echo "$cnt $n"
done
echo "END: $n"
我省略了所有的“$”(如果可能的话,遵循拉基布的评论)。请参阅布须曼的答案以获得更直接的携带处理。
这其他系列是:
]# for ((z=1; z < 10000; z+=2)) do s=$((s + z)); done
]# echo $s
25000000
]# echo $(( (1+9999) * 2500 ))
25000000
这最后的9位数字2^5001
是
]# echo ${n:${#n}-9}
383818752
这可以添加,无需技巧:
]# echo $((383818752 + 25000000))
408818752
我认为还有负 2 需要记住,因为我总结 2+4+8+16... 系列的方式。
所以我们有一个echo ${#n}
1506 位数字,从echo ${n:0:10}
2824934064 开始,到 ...408818750 结束。其他 1487 位数字:见上文。
当然,完整的解决方案是真正生成(两个)系列并逐一添加项目,直到添加了 10,000 个。但这需要一个更通用的字符串计算器,然后几何级数的项目本身就会变得太大。
这个想法是,数字非常大,但所需的运算非常简单:只需乘以 2。并且加法可以简化:
2+4+8+16 = 32 - 2
(或者1+2+4+8 = 15 = "F" hex = "1111" bin = 2^4 - 1
)
所以你的总和之一是2^5001 - 2
。至少bc
给出相同的前 10 位数字 - 整个数字很容易显示在屏幕上。
在里面bc
,通过一些重新排列,你可以直接得到它:
2^5001 - 2 + 10^8/4
28249340642788520736704193340322946673377923503690822336273761717142\
36339685415025116178252633423052746712064168627321655284076761399586\
76671942371453279846862103555703730798023755999290263414138746996425\
26264750510622243074568807190180107190972146683690681115113347360313\
11748109293992809981016993989447158018112351427532364564328684263630\
41983113354252997303564408348123661878478353722682766588036480451677\
38545119229401028848656215055125899067818762639793347126721265938204\
76849082516717773137462679625744819600176761473364436085288658217880\
61578040438881156396976534679536477744559804314840614495141020847691\
73774519347178361163745559287150603703617328271202570260509345364601\
85004366560365038146804908997263665312759757243970220927259709238991\
74562238279814456008771885761907917633109135250592173833771549657868\
89988272483317735065388066512220732911396524441366894843962216374480\
98590069639827534807596519975828237596054351677709971502305989434869\
38482234140460796206757230465587420581985312889685791023660711466304\
04160831584018008362390376091341103093669889236546348465537197855521\
52414190517566375329767366979300309499957282395308828667138560246882\
23531470672787115758429874008695136417331917435528118587185775028585\
68711409417832975296623323138377240762599511138034378433946751044893\
80649501575956618026431598802546744213887545668798445605481215964695\
73480869786916240396682202067625013440093219782321400568004201960905\
92807957740867060523867519572410438456074296226432829437302833818183\
4408818750
奇数之和 (1+3+5+7...),直到第 n 个数字,只是 n 平方,正如另一个问题中所指出的。这对于伽利略来说是众所周知的(维基百科没有明确提及)。这(n+1)^2
是n^2 + 2n + 1
通过放大一个正方形来说明的:您需要两个“条”加上“角”:
...1
...1
...1
222X
将 1 到 100 的所有数字相加的“技巧”是我 40 年前从我的数学老师那里听到的,有一个关于欧拉(或高斯)的好故事,他在学校被告知要计算它 - 老师想要一个安静的时间。但五分钟后,未来天才就完成了,变成1+2+3+4+5+6...+100
了:
1 + 100 +
2 + 99 +
3 + 98 +
...
9 + 92 +
10 + 91 +
...
50 + 51
总和是50 * 101
.困难的部分是确保“配对”正确。
所以我用了5000/2 * (1+9999)
或10^4/4 * 10^4
,这和 是一样的5000^2
。一般的:(n/2)^2 = n^2 / 4 = n * n/4
。我不知道这是否符合逻辑或令人困惑。
挑战仍不清楚。但在我看来,循环bc
似乎太简单了。我把它转过来并直接对级数求和(作弊)——由于数字巨大,我仍然需要 5000 次迭代,和不bc
。
答案4
如果我正确理解了挑战,则要总计的两个系列是:
k 2^k 2*k-1
1 2 1
2 4 3
3 8 5
4 16 7
...
k 值最大为 5000(系列 1 的 5000 个项目和系列 2 的 5000 个项目)。
2^k
接近末尾时 k 产生的数字相当大。 shell 算术无法处理如此大的数字,但bc
可以。
bc 中的一个简短脚本可以执行整个计算:
$ bc <<<"n=5000;"'while(k++<n){sum+=(2^k+k*2-1)};sum'
28249340642788520736704193340322946673377923503690822336273761717142\
36339685415025116178252633423052746712064168627321655284076761399586\
76671942371453279846862103555703730798023755999290263414138746996425\
26264750510622243074568807190180107190972146683690681115113347360313\
11748109293992809981016993989447158018112351427532364564328684263630\
41983113354252997303564408348123661878478353722682766588036480451677\
38545119229401028848656215055125899067818762639793347126721265938204\
76849082516717773137462679625744819600176761473364436085288658217880\
61578040438881156396976534679536477744559804314840614495141020847691\
73774519347178361163745559287150603703617328271202570260509345364601\
85004366560365038146804908997263665312759757243970220927259709238991\
74562238279814456008771885761907917633109135250592173833771549657868\
89988272483317735065388066512220732911396524441366894843962216374480\
98590069639827534807596519975828237596054351677709971502305989434869\
38482234140460796206757230465587420581985312889685791023660711466304\
04160831584018008362390376091341103093669889236546348465537197855521\
52414190517566375329767366979300309499957282395308828667138560246882\
23531470672787115758429874008695136417331917435528118587185775028585\
68711409417832975296623323138377240762599511138034378433946751044893\
80649501575956618026431598802546744213887545668798445605481215964695\
73480869786916240396682202067625013440093219782321400568004201960905\
92807957740867060523867519572410438456074296226432829437302833818183\
4408818750
这需要几秒钟。更快的方法是避免在每个循环上重新计算指数,并e*=2
在每个循环上使用 var,仅通过乘法即可得出 2 的下一个幂。
$ bc <<<"n=5000;"'e=2;o=1;while(k++<n){sum+=e+o;e*=2;o+=2}; sum'
其产生相同的结果并且只需要 0.1 秒。
甚至还可以改进。已知各级数的k项之和为:
总和{1}{k}( 2^j ) = 2^(k+1)-2 权力总和
总和{1}{k}( 2*j-1 ) = k^2 奇数之和
因此,没有任何循环(非常快,10 毫秒)的结果是这样的数学计算:
echo "k=5000; 2^(k+1)-2+k^2" | bc
并且,仅打印前 10 位数字:
$ echo "k=5000; sum=2^(k+1)-2+k^2;sum/10^(length(sum)-10)" | bc
2824934064