Одномерный массив Опции

[ammaximus]

Задача 4.
Числа от 1 до n расставлены по кругу. Вычеркиваем каждое второе число, начиная с 1. Написать программу, которая определит какое число останется последним и напечатает его. Исходное натуральное число - 1<n=<=1 000 000. Общий случай: определите количество шагов для произвольного числа.

Я что-то накорябал по разложению n на простые множители, дальше не знаю что... Работает не для всех чисел.

[Michael_Rybak]

Эта задача решается за линейное время. Пусть мы знаем, кто умрет последним, если всего у нас 9 человек, и начинаем с первого. Тогда чтобы узнать, кто умрет последним при n = 10, мы просто мысленно убиваем 1го, должным образом перенумеровываем оставшихся, и применяем ответ для n = 9. Делается это за константу. Несложно записать общее рекуррентное соотношение.

Решение займет всего несколько строк:

...
var f: array [1 .. 1000000] of longint;
...
begin
  Readln(n);
  f[1] := 1;
  for i := 2 to n do
    f[i] := ...
  Writeln(f[n]);
end.

Задача посложнее - вывести всех в порядке наступления смерти. Тут уже, наверное, только за n log n можно. Надо будет - расскажу.