 Одномерный массив |
Прочтите прежде чем задавать вопрос!
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
  |
| ammaximus |
 23.12.2006 15:17
Сообщение
#1
|
 Ночной волк  Группа: Пользователи Сообщений: 103 Пол: Мужской Репутация:  1   |
Задача 4.
Числа от 1 до n расставлены по кругу. Вычеркиваем каждое второе число, начиная с 1. Написать программу, которая определит какое число останется последним и напечатает его. Исходное натуральное число - 1<n=<=1 000 000. Общий случай: определите количество шагов для произвольного числа. Я что-то накорябал по разложению n на простые множители, дальше не знаю что... Работает не для всех чисел.  -------------------- Не думай о белой обезьяне.
|
   |
 
|
| volvo |
23.12.2006 15:18
Сообщение
#2
|
|
Гость |
В поиск по слову "Казнь"
|
|
|
|
| Michael_Rybak |
23.12.2006 16:34
Сообщение
#3
|
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Эта задача решается за линейное время. Пусть мы знаем, кто умрет последним, если всего у нас 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 16:39
Сообщение
#4
|
|
Гость |
Цитата Решение займет всего несколько строк: Вот только, чтобы ЗАСТАВИТЬ эти несколько строк работать под Турбо-Паскалем ты напишешь еще несколько сотен...  |
|
|
|
| Michael_Rybak |
23.12.2006 17:26
Сообщение
#5
|
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Да ладно, Вольво. Во-первых, почему обязательно Турбо. Во-вторых, хранить все предыдущие значения f[] не нужно, достаточно только двух переменных (если ты имеешь ввиду допустимый размер массива). Так что *я* не напишу еще несколько сотен ;)
|
|
|
|
| volvo |
23.12.2006 17:50
Сообщение
#6
|
|
Гость |
Ну, и в третьих - задача ВООБЩЕ без массивов решается...
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.
 Сделаешь программу на массивах, работающую быстрее? |
|
|
|
| Malice |
23.12.2006 18:21
Сообщение
#7
|
 Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
Может что в условии не понял, но мне кажется вот эти 2 строки друг другу противоречат:
Цитата(volvo @ 23.12.2006 17:50)  if pred = n then last := 1 Цитата Вычеркиваем каждое второе число, начиная с 1. Т.е. первый не может остаться последним, т.к. вылетел первым |
|
|
|
| volvo |
23.12.2006 18:25
Сообщение
#8
|
|
Гость |
 Начиная с первого ОТСЧИТЫВАЕМ числа, т.е. первым вылетает второй... |
|
|
|
| Michael_Rybak |
24.12.2006 19:03
Сообщение
#9
|
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата(volvo @ 23.12.2006 16:50) Ну, и в третьих - задача ВООБЩЕ без массивов решается... А в-четвертых, браво!  Я потратил кучу времени только чтобы понять и доказать правильность твоего решения. Интересно было бы узнать, как ты его получил, а также услышать твое доказательство. |
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 18.07.2025 20:27 |