Одномерный массив |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Одномерный массив |
ammaximus |
Сообщение
#1
|
Ночной волк Группа: Пользователи Сообщений: 103 Пол: Мужской Репутация: 1 |
Задача 4.
Числа от 1 до n расставлены по кругу. Вычеркиваем каждое второе число, начиная с 1. Написать программу, которая определит какое число останется последним и напечатает его. Исходное натуральное число - 1<n=<=1 000 000. Общий случай: определите количество шагов для произвольного числа. Я что-то накорябал по разложению n на простые множители, дальше не знаю что... Работает не для всех чисел. -------------------- Не думай о белой обезьяне.
|
volvo |
Сообщение
#2
|
Гость |
В поиск по слову "Казнь"
|
Michael_Rybak |
Сообщение
#3
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Эта задача решается за линейное время. Пусть мы знаем, кто умрет последним, если всего у нас 9 человек, и начинаем с первого. Тогда чтобы узнать, кто умрет последним при n = 10, мы просто мысленно убиваем 1го, должным образом перенумеровываем оставшихся, и применяем ответ для n = 9. Делается это за константу. Несложно записать общее рекуррентное соотношение.
Решение займет всего несколько строк: ... Задача посложнее - вывести всех в порядке наступления смерти. Тут уже, наверное, только за n log n можно. Надо будет - расскажу. |
volvo |
Сообщение
#4
|
Гость |
Цитата Решение займет всего несколько строк: Вот только, чтобы ЗАСТАВИТЬ эти несколько строк работать под Турбо-Паскалем ты напишешь еще несколько сотен... |
Michael_Rybak |
Сообщение
#5
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Да ладно, Вольво. Во-первых, почему обязательно Турбо. Во-вторых, хранить все предыдущие значения f[] не нужно, достаточно только двух переменных (если ты имеешь ввиду допустимый размер массива). Так что *я* не напишу еще несколько сотен ;)
|
volvo |
Сообщение
#6
|
Гость |
Ну, и в третьих - задача ВООБЩЕ без массивов решается...
constСделаешь программу на массивах, работающую быстрее? |
Malice |
Сообщение
#7
|
Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
|
volvo |
Сообщение
#8
|
Гость |
Начиная с первого ОТСЧИТЫВАЕМ числа, т.е. первым вылетает второй...
|
Michael_Rybak |
Сообщение
#9
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
|
Текстовая версия | 29.03.2024 12:57 |