Представьте, что Вы - хакер.
В Ваши руки попала вражеская секретная программа.
Вам нужно понять, что она делает.
Вы декодировали машинные инструкции и получили программу на алгоритмическом языке:
1. Алгоритм, вычисляющий X(M,N)
Вход: M, N
Выход: X
X=0
A=1
пока M не нуль, выполнять
если M нечётно, то
M=M-N
X=X+A
конец если
A=A+A
M=[M/2]
конец пока
Что этот кусок программы делает?
Что это за функция такая X(M,N) ?
Ответ дать простыми словами.
2. Алгоритм, вычисляющий Y(N)
Y=1
A=2*(N mod 2)
B=2*(1-A)
повторить [(N+1)/2] раз
A=A+B
B=B+8
Y=Y*max(1,A)
конец повторить
3. Алгоритм, вычисляющий Z(N)
Определим последовательность A(1)..A(14) = 91, 85, 51, 38, 33, 29, 23, 19, 17, 13, 11, 14, 2, 1
Определим последовательность B(1)..B(14) = 17, 78, 19, 23, 29, 77, 95, 77, 1, 11, 13, 15, 15, 55
M=2
повторить N раз
повторять
K=0
повторять
K=K+1
пока A(K) не будет делителем M
M=B(K)*M/A(K)
пока M не станет степенью двойки
конец повторить
Z=log2(M)
|
Um_nik
Гость
|
 |
� Ответ #30 : Февраль 03, 2011, 11:45:02 � |
|
N принадлежит Z
N>-1
Z=N+1
|
|
|
|
|
Записан
|
|
|
|
VVV
Умник
 Offline
Сообщений: 662
СПАСИБО
-вы поблагодарили: 20
-вас поблагодарили: 55
|
|
� Ответ #31 : Февраль 03, 2011, 11:48:30 � |
|
А -7 на 7 этот алгоритм делит нацело?
|
|
|
|
|
Записан
|
Правила и тактика игры в "ассоциации". //текст доступен после регистрации// . Дополнительные методы, архив партий //текст доступен после регистрации// . |
|
|
|
Um_nik
Гость
|
|
� Ответ #32 : Февраль 03, 2011, 11:55:02 � |
|
Умник, объясни мне, я не поняла
Если Н - четное, то А=2*0=0, а В=2*(1-0)=2 Начинаем раз за разом делать цикл: А=2 В=10 А=12 В=18 А=30 В=26 и т.д. Замечаем, что А=2=1*2 А=12=3*4 А=30=5*6 Теперь смотрим, как они увеличиваются 3*4=4+4+4 4*5=4+4+4+4+4 А(А+1)-(А-1)А=2А (А+2)(А+1)-(А+1)А=2(А+1) (А+2)(А+1)-(А-1)А=4А+2 У нас А увеличивается на 2, значит разница увеличивается на 8. *Это было такое сумбурное доказательство как бэ по индукции* Ну и для нечетных примерно так же доказывается. Основная идея доказательства: не надо у меня спрашивать, как я решил, я сам не знаю) |
|
|
|
|
Записан
|
|
|
|
|
seamew
Гость
|
|
� Ответ #33 : Февраль 03, 2011, 12:03:22 � |
|
мне кажется, я туповата...
|
|
|
|
|
Записан
|
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #34 : Февраль 03, 2011, 13:01:04 � |
|
А -7 на 7 этот алгоритм делит нацело?
ну вот, начали придираться  |
|
|
|
|
Записан
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #35 : Февраль 03, 2011, 13:02:42 � |
|
N принадлежит Z
N>-1
Z=N+1
нет |
|
|
|
|
Записан
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
Strike
Давненько
Offline
Сообщений: 52
СПАСИБО
-вы поблагодарили: 7
-вас поблагодарили: 5
|
|
� Ответ #36 : Февраль 03, 2011, 13:04:42 � |
|
3) log2(15)  |
|
|
|
|
Записан
|
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #37 : Февраль 03, 2011, 13:05:33 � |
|
3) log2(15) ответ = константа для любого входного N ? неверно |
|
|
|
|
Записан
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
Strike
Давненько
Offline
Сообщений: 52
СПАСИБО
-вы поблагодарили: 7
-вас поблагодарили: 5
|
|
� Ответ #38 : Февраль 03, 2011, 13:10:22 � |
|
3) log2(15) ответ = константа для любого входного N ? неверно А log2(15) разве не константа ?(от N не зависит) |
|
|
|
|
Записан
|
|
|
|
Strike
Давненько
Offline
Сообщений: 52
СПАСИБО
-вы поблагодарили: 7
-вас поблагодарили: 5
|
|
� Ответ #39 : Февраль 03, 2011, 13:13:20 � |
|
хоть возможно и z = 1  |
|
|
|
|
Записан
|
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #40 : Февраль 03, 2011, 13:14:12 � |
|
ответ не должен быть константой, он зависит от N
|
|
|
|
|
Записан
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
|
Um_nik
Гость
|
|
� Ответ #41 : Февраль 03, 2011, 13:26:26 � |
|
Че нет-то?)))
|
|
|
|
|
Записан
|
|
|
|
VVV
Умник
Offline
Сообщений: 662
СПАСИБО
-вы поблагодарили: 20
-вас поблагодарили: 55
|
|
� Ответ #42 : Февраль 03, 2011, 13:39:33 � |
|
Кто-нибудь посчитал Z(1), Z(2), Z(3)? Неплохо бы программку написать. Многовато вычислений.
|
|
|
|
|
Записан
|
Правила и тактика игры в "ассоциации". //текст доступен после регистрации// . Дополнительные методы, архив партий //текст доступен после регистрации// . |
|
|
Strike
Давненько
Offline
Сообщений: 52
СПАСИБО
-вы поблагодарили: 7
-вас поблагодарили: 5
|
|
� Ответ #43 : Февраль 03, 2011, 13:43:36 � |
|
где в этом алгоритме видно, что Z зависит отN ? |
|
|
|
|
Записан
|
|
|
|
|
Um_nik
Гость
|
|
� Ответ #44 : Февраль 03, 2011, 14:14:49 � |
|
Если на входе M=2^n, то на выходе будет M=2^(n+1)
(Только что посчитал специально, раз уж Дискоед сказал, что неправильно. Могу выложить решение)
Соответственно, если М=2^1 и повторять цикл N раз, то на выходе получится М=2^(N+1)
Ну и Z=log2(2^(N+1))=N+1
Где ошибка?
|
|
|
|
|
Записан
|
|
|
|
|
