Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Одномерный массив

Автор: ammaximus 23.12.2006 19:17

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

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

Автор: volvo 23.12.2006 19:18

В поиск по слову "Казнь"

Автор: Michael_Rybak 23.12.2006 20:34

Эта задача решается за линейное время. Пусть мы знаем, кто умрет последним, если всего у нас 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 можно. Надо будет - расскажу.

Автор: volvo 23.12.2006 20:39

Цитата
Решение займет всего несколько строк:
Вот только, чтобы ЗАСТАВИТЬ эти несколько строк работать под Турбо-Паскалем ты напишешь еще несколько сотен... lol.gif

Автор: Michael_Rybak 23.12.2006 21:26

Да ладно, Вольво. Во-первых, почему обязательно Турбо. Во-вторых, хранить все предыдущие значения f[] не нужно, достаточно только двух переменных (если ты имеешь ввиду допустимый размер массива). Так что *я* не напишу еще несколько сотен ;)

Автор: volvo 23.12.2006 21:50

Ну, и в третьих - задача ВООБЩЕ без массивов решается...

const
n:longint = 12;

var
last, i, pred: longint;
begin
pred := $0001;
while pred < n do
pred := pred shl 1;
if pred = n then last := 1
else
begin
pred := pred shr 1;
last := 1 + 2*(n - pred);
end;

writeln('оставшееся число:', last);
end.
smile.gif Сделаешь программу на массивах, работающую быстрее?

Автор: Malice 23.12.2006 22:21

Может что в условии не понял, но мне кажется вот эти 2 строки друг другу противоречат:

Цитата(volvo @ 23.12.2006 17:50) *

if pred = n then last := 1

Цитата
Вычеркиваем каждое второе число, начиная с 1.

Т.е. первый не может остаться последним, т.к. вылетел первым smile.gif

Автор: volvo 23.12.2006 22:25

no1.gif Начиная с первого ОТСЧИТЫВАЕМ числа, т.е. первым вылетает второй...

Автор: Michael_Rybak 24.12.2006 23:03

Цитата(volvo @ 23.12.2006 16:50) *

Ну, и в третьих - задача ВООБЩЕ без массивов решается...


А в-четвертых, браво! good.gif Я потратил кучу времени только чтобы понять и доказать правильность твоего решения. Интересно было бы узнать, как ты его получил, а также услышать твое доказательство.