☰

数値シーケンス配列を2つ作成し、それらを断続的にリンクする方法は？ (しゃっくり)

tag-icon • tag-icon bash shell-script shell
数値シーケンス配列を2つ作成し、それらを断続的にリンクする方法は？ (しゃっくり)

私は次のような挑戦を受けました：

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 から始まり、10,000 個の数字に達するまで倍増する配列を作成します。

二つ目は

2. 数字 1 から始まり、10,000 個の数字に達するまで 2 を追加して配列を作成します。

次に、次を含む3番目の配列があります。

3. 2つの配列を結合しましたが、これは{value1FromArray1、value1FromArray2、value2FromArray1、value2FromArray2...}と同じです。

今私が考えている唯一のことは...私の方法は仕事をするようですが、非常に非効率的です。 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

シェル (/bin/sh または /bin/bash) で実行される 1 行のコマンド:

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 を減算して加算する2^5001必要があります。その他シリーズ、1+3+5+7... (下記参照)

私が理解したのは、正確な結果を得ることが課題です。最初の10桁の数字は解決策ではなく、迅速な確認です。

これは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"

すべての「$」を省略しました（可能であればRakibのコメントに従います）。より簡単なキャリー処理については、Bushmanの回答を参照してください。

これその他シリーズは次のとおりです。

]# 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+4+8+16... シリーズをまとめる方法のために覚えておくべきマイナス2もあると思います。

したがって、2824934064で始まり、408818750で終わるecho ${#n}1506桁の数字があります。echo ${n:0:10}その他1487桁：上記を参照してください。

もちろん、完全な解決策は実際にシリーズ（2つ）を作成し、10,000個が追加されるまで項目を1つずつ追加することです。ただし、これにはより一般的な文字列計算機が必要です。これにより、幾何学系列項目自体が大きくなりすぎます。

アイデアは数字が非常に大きいということです。しかし、必要な作業は非常に簡単です。 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

他の質問で指摘したように、n番目の数字までの奇数（1 + 3 + 5 + 7 ...）の合計はnの2乗にすぎません。これはガリレオにもよく知られていました（Wikipediaではこれについて明示的に言及していません）。これは長方形を拡大することによって説明(n+1)^2されます。 2つの「バー」と「コーナー」が必要です。n^2 + 2n + 1

...1
...1
...1
222X

1から100までのすべての数字を加える「秘法」は、40年前に数学の先生から聞いたことです。オイラー（またはガウス）が学校で計算するように聞いた素晴らしい話があります。先生は静かな時間が欲しい。時間。しかし、5分後、将来の天才は完成し、次のようになりました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)orを使用しました。共通: 。これが論理的なのか混乱しているのかわかりません。10^4/4 * 10^45000^2(n/2)^2 = n^2 / 4 = n * n/4

課題はまだ不明です。しかし、bc私の考えでは、ループは単純すぎるようです。私はそれを裏返してシリーズを直接合計しました（トリック）。数字が途方もないので、まだ5000回の繰り返しが必要でした。そしていいえbc。

答え4

私がチャレンジを正しく理解したら、合計になる2つのシリーズは次のとおりです。

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^kkが終わるにつれて生成される数字はかなり大きい。シェル操作はこのように大きな数字を処理できませんが、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秒しかかかりません。

改善することもできます。各系列のｋ項の和は以下の通りである。

合計{1}{k}( 2^j ) = 2^(k+1)-2 総電力
合計{1}{k}( 2*j-1 ) = k^2 奇数の合計

したがって、ループなし（非常に高速、10ms）の結果は次のようになります。

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

関連情報