Форум умных людей

Представьте, что Вы - хакер.
В Ваши руки попала вражеская секретная программа.
Вам нужно понять, что она делает.
Вы декодировали машинные инструкции и получили программу на алгоритмическом языке:

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=log₂(M)

X=[M/N]

проверь при M=1, N=2

Так это будет бесконечный алгоритм

Значит, ты его не понял

Так может, "пока М больше нуля"?

Твой алгоритм, М=1 N=2
М - нечетное
М=М-N=1-2=-1
М - нечетное
М=М-N=-1-2=-3
и т.д.

ты подгоняешь алгоритм под свою функцию
а надо найти функцию, которую вычисляет этот алгоритм

Подожди.
Если М=1 N=2 , что будет на выходе?
У меня по твоему алгоритму получается Х=бесконечность

Умник, а это то действие всегда выполняется:
A=A+A
M=[M/2]

Почему?
Как я понял, оно выплняется только тогда, когда М - не нечетное, т.е. четное.

неправильно понял


на этом наборе значений функция не определена
а твоя определена

нет, если М-нечетное, то выполняется
M=M-N
X=X+A

Это выполняется в любом случае:
A=A+A
M=[M/2]

 Про то, что М долно быть четно нет не слова.
и условия тоже нет

то есть, если М - четно, то ничего не выполняется?

как-то у меня была задача по информатике:

Заданы функции:
 (http://savepic.org/1307674.gif)
 
(http://savepic.org/1295386.gif)

Найти оптимальное значение параметра a2=a*  по критерию
 
(http://savepic.org/1288218.gif)

d – абсцисса точки пересечения графиков функций (http://savepic.org/1293338.gif)  и (http://savepic.org/1281050.gif) .
 
сигма1=сигма2=0.5
а1=2
с=1
е=4

тут решение находится подбором...
ну то есть сначала "метод половинного деления", потом "метод золотого сечения" и т.д.
мне чем-то напомнило... может, тут тоже функция с двумя неизвестными...

Ладно, не буду мучить, ответ на первое задание:
Показать скрытый текст

Первый пост обновлён, добавлена вторая программа

Да боже ж ты мой, объясните мне хоть кто-нибудь наконец, что такое mod ???

Y=N! при четных N
Y=0 при нечетных N

a mod b - остаток от деления a на b

мод - это остаток от деления
M mod N может быть от 0 до N-1

неправильно

а почему до N-1?
то есть
5 mod 2 = 1? я правильно поняла?

Ну N принадлежит Z, N>-2
при N=-1 Y=1
при N=0 Y=1
при N=2k Y=N!, где k - целое число
при N=2k+1 Y=0, где k - целое число

Потому что сотаток не может быть больше или равен делителю.
ага

у тебя ошибка
ищи

А [5,5]=5? или 6?

Y=1                                                  
A=2*(N mod 2)        
B=2*(1-A)

    раз N нечетное, то получается A=2 B=-2                            

повторить [(N+1)/2] раз
   A=A+B
A=2-2 = 0
   B=B+8
B=6
   Y=Y*max(1,A)
конец повторить

повторить [(N+1)/2] раз

5

   Первый алгоритм не осуществляет деления нацело на нечетное число. Лишь в редких случаях. Чему равно 8 div 7 по этому алгоритму?

Аа, просто Y=N!
ну и при N=-1 Y=1

"Деление нацело" - это когда числа делятся нацело
А то деление, которое обычное - это "деление с остатком"
Алгоритм не вычисляет div
для чисел 8 и 7 он и не должен ничего вычислять

ну наконец-то!


Смотрите третью задачку, она посложнее

Умник, объясни мне, я не поняла

N принадлежит Z
N>-1
Z=N+1

  А -7 на 7 этот алгоритм делит нацело?

Если Н - четное, то А=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.
*Это было такое сумбурное доказательство как бэ по индукции*

Ну и для нечетных примерно так же доказывается.

Основная идея доказательства: не надо у меня спрашивать, как я решил, я сам не знаю)

мне кажется, я туповата...

ну вот, начали придираться :)

нет

3) log2(15) :-\

ответ = константа для любого входного N ?
неверно

А log2(15) разве не константа ?(от N не зависит)

хоть возможно и z = 1 ???

ответ не должен быть константой, он зависит от N

Че нет-то?)))

  Кто-нибудь посчитал Z(1), Z(2), Z(3)? Неплохо бы программку написать. Многовато вычислений.

где в этом алгоритме видно, что Z зависит отN ??? :-\ ?

Если на входе M=2^n, то на выходе будет M=2^(n+1)
(Только что посчитал специально, раз уж Дискоед сказал, что неправильно. Могу выложить решение)
Соответственно, если М=2^1 и повторять цикл N раз, то на выходе получится М=2^(N+1)
Ну и Z=log₂(2^(N+1))=N+1

Где ошибка?

В вычислениях где-то
Запусти на компьютере, увидишь правильные Z(1),Z(2),...

Я не программист

И чо, даже программируемого калькулятора в руках не держал?

Это типа МК-** ?
Держал, у бабушки :D

так у тебя бабушка на нём программирует?
 ;D

Возможно ;D

   Maple говорит, что Z(i) - это  i-ое простое число.

Трудно не верить Maplу :)

   Продолжение следует? Maple требует продолжения банкета.

так мапл только подсказку дал наводящую
теперь это нужно доказать

    Надо думать. Выглядит все загадочно.