|
|
back to boardMy Solution is here Posted by vetas 28 Dec 2008 13:48 ## Russian ## ## 1 Идея ## 1) Представим число A в виде 10x+m1, где x - число десятков m1=2 (m1 не может быть равно 1, так как в этом случае искомое число A нечетное и на 2^N не разделится). Разделим число на 2, получим A=5x+1. 2) Пусть x=10y+m2, где y - число сотен. После подстановки получим A=5(10y+m2)+1=50y+5m2+1. Чтобы число A разделилось на 2, надо, чтобы m2 было нечетным. Следовательно выбираем m2=1. После деления на 2 получим: A=(50y+5*1+1)/2=25y+3. 3) Пусть y=10z+m3, где z - число тысяч. После подстановки получим A=25(10z+m3)+3=250z+25m3+3. Чтобы число A разделилось на 2, надо, чтобы m3 было нечетным. Следовательно выбираем m3=1. После деления на 2 получим: A=(250z+25*1+3)/2=125z+14. 4) Пусть z=10t+m4, где t - число десятков тысяч. После подстановки получим A=125(10t+m4)+14=1250t+125m4+14. Чтобы число A разделилось на 2, надо, чтобы m4 было четным. Следовательно выбираем m4=2. После деления на 2 получим: A=(1250t+125*2+14)/2=625t+132. Далее процесс повторяется N раз. Последовательность mN...m4m3m2m1 образует ответ. Алгоритм требует применения длинной арифметики. Общее решение достигается за N шагов. ## 2 Алгоритм ## Пусть m[1]=2; a_[1]=5; b_[1]=1; Цикл i = от 2 до n нц m_[i]=(если b_[i-1] нечетное, то 1, иначе 2) b_[i]=(если b_[i-1] нечетное, то (a_[i-1]+b_[i-1])/2, иначе (2*a_[i-1]+b_[i-1])/2) (так как a_[i-1] нечетное всегда по определению) a_[i]=a_[i-1]*5; кц ## English (in short) ## ## 1 The Idea ## 1) Let me A = 10x+m1, where x - number of Tens m1=2 (m1<>1, as A - odd). Division A in 2, let's receive A=5x+1. 2) Let me x=10y+m2, where y - number of Hundreds. Then A=5(10y+m2)+1=50y+5m2+1. if A%2==0, m2 is odd. Then m2=1 and A=(50y+5*1+1)/2=25y+3. 3) Let me y=10z+m3, where z - number of Thousand. Then A=25(10z+m3)+3=250z+25m3+3. if A%2==0, m3 is odd. Then m3=1 and A=(250z+25*1+3)/2=125z+14. 4) Let me z=10t+m4, где t - number of Tens thousand. Then A=125(10t+m4)+14=1250t+125m4+14. if A%2==0, m3 is even. Then m3=1 and A=(1250t+125*2+14)/2=625t+132. Further process repeats N time. Sequence mN... m4m3m2m1 forms the answer. The algorithm demands application of long arithmetics. ## 2 The Algo ## Let me m[1]=2; a_[1]=5; b_[1]=1; for i = 2 to n begin m_[i]=(if b_[i-1] is odd, then 1, else 2) b_[i]=(if b_[i-1] is odd, then (a_[i-1]+b_[i-1])/2, else (2*a_[i-1]+b_[i-1])/2) a_[i]=a_[i-1]*5; end Re: My Solution is here thank you! excellent idea! Re: My Solution is here Можно проще. Индукция: для любого n существует число x(n) из 1 и 2 длиной n, делящееся на 2^n. База: n=1=>x(1)=2. Переход n->n+1: если x(n) делится на 2^(n+1), то в качестве x(n+1) можно взять x(n+1)=2x(n) (т.е. слева приписать 2), иначе x(n+1)=1x(n). Re: My Solution is here Posted by Sadeko 6 Mar 2019 15:44 Edited by author 10.03.2019 13:22 |
|
|