☰

숫자 시퀀스 배열 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. 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

셸(/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를 빼고 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개가 추가될 때까지 항목을 하나씩 추가하는 것입니다. 그러나 이를 위해서는 보다 일반적인 문자열 계산기가 필요하며, 그러면 기하학적 계열 항목 자체가 너무 커질 것입니다.

아이디어는 숫자가 매우 크다는 것입니다. 그러나 필요한 작업은 매우 간단합니다. 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 제곱에 불과합니다. 이것은 갈릴레오에게도 잘 알려져 있었습니다(Wikipedia에서는 이에 대해 명시적으로 언급하지 않았습니다). 이는 사각형을 확대하여 설명 (n+1)^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

내가 챌린지를 올바르게 이해했다면 총계가 되는 두 시리즈는 다음과 같습니다.

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초밖에 걸리지 않습니다.

심지어 개선될 수도 있습니다. 각 계열의 k 항의 합은 다음과 같습니다.

합계{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

관련 정보