IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Одномерный массив
сообщение
Сообщение #1


Ночной волк
**

Группа: Пользователи
Сообщений: 103
Пол: Мужской

Репутация: -  1  +


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

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


--------------------
Не думай о белой обезьяне.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






В поиск по слову "Казнь"
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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 можно. Надо будет - расскажу.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






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


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Да ладно, Вольво. Во-первых, почему обязательно Турбо. Во-вторых, хранить все предыдущие значения f[] не нужно, достаточно только двух переменных (если ты имеешь ввиду допустимый размер массива). Так что *я* не напишу еще несколько сотен ;)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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.
smile.gif Сделаешь программу на массивах, работающую быстрее?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


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

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

if pred = n then last := 1

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

Т.е. первый не может остаться последним, т.к. вылетел первым smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






no1.gif Начиная с первого ОТСЧИТЫВАЕМ числа, т.е. первым вылетает второй...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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


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

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 12:57
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name