0 / 0 / 0
Регистрация: 06.10.2010
Сообщений: 28
|
||||||
1 | ||||||
Считалочка - выбытие игроков, пока не останется три человека13.10.2010, 22:27. Показов 8730. Ответов 21
В круг выстраивается N-человек (N<50000). Начиная с первого, неизменно движутся по кругу и исключают каждого М-ого. Когда кто-то выбывает, круг смыкается. Счёт начинается заново со следующего человека в круге.
Процесс продолжается пока не остается ровно 3 человека.
0
|
13.10.2010, 22:27 | |
Ответы с готовыми решениями:
21
Найти номер человека который останется в живых Повторять n = f(n) до тех пор, пока в n не останется один разряд Рекурсивные функции. Разделение эл. массива, пока не останется 1 элемент Суммировать числа до тех пор, пока не останется 1 число |
13102 / 5883 / 1706
Регистрация: 19.09.2009
Сообщений: 8,808
|
|||||||||||
14.10.2010, 09:45 | 2 | ||||||||||
Сообщение было отмечено Памирыч как решение
Решение
Если решать в консоли Delphi, то можно и через массивы:
Размер одного сегмента = 2^16 = 65536 байт. Размер массива: 50000 * SizeOf(Word) = 50000 * 2 = 100000 байт. Поэтому, в самом деле, как предлагают Puporev и lexus_ilia, видимо, придётся реализовывать через связанный список. --- Если задание не запрещает устанавливать количество участников меньшее, чем 50000, тогда в Pascal можно использовать такой код:
2
|
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
||||||
14.10.2010, 09:58 | 3 | |||||
Сообщение было отмечено как решение
Решение
Вот, что у меня получилось, но не советую вводить N>31042, потому что вылетает Stack overflow error (Это в Turbo Pascal'e 7.0, нет возможности проверить на других паскалях):
4
|
Почетный модератор
64299 / 47594 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
|
|||||||||||
14.10.2010, 10:50 | 4 | ||||||||||
Сообщение было отмечено как решение
Решение
Код, предложенный Mawrat, для консоли Делфи , почему-то выдает в Паскаль АВС ошибку выхода за диапазон в строке
Добавлено через 18 минут Кстати взял в Турбо Паскале N=32000, считает быстрее чем в АВС при N=10000.
4
|
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
|
15.10.2010, 00:09 | 5 |
Так а у кого-нибудь есть под рукой FPC чтобы проверить мой вариант ? Поставьте точку остановки сразу после добавления всех элементов, если не вылетит, то всё ок.
1
|
13102 / 5883 / 1706
Регистрация: 19.09.2009
Сообщений: 8,808
|
|
15.10.2010, 10:11 | 6 |
Lexus_ilia, я твой код запускал в консоли Delphi и в Borland Pascal. Условия: 50000 участников, интервал счёта 25000. Система: Windows XP Pro SP3, двухядерный проц. 2.33 Ггц. Везде отработало без ошибок.
По скорости выполнения: В Delphi: 15 секунд. В Pascal: 57 секунд. Если через массивы в консоли Delphi- скорость больше. Но это и понятно - для обработки динамических списков требуется гораздо больше вычислений.
2
|
Почетный модератор
64299 / 47594 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
|
|
15.10.2010, 10:44 | 7 |
Эта программа в Фрее у меня на фиговом компьютере считала 77 секунд.
Добавлено через 6 минут На том же фиговом, но в консоли Делфи считало 30 секунд, ответ сошелся....
2
|
3067 / 727 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
|
|
15.10.2010, 23:37 | 8 |
Отлично, значит не зря писал) Я очень рад, спасибо, что протестировали...
2
|
0 / 0 / 0
Регистрация: 06.10.2010
Сообщений: 28
|
|
20.10.2010, 20:25 [ТС] | 9 |
всем большое спасибо
0
|
7 / 7 / 4
Регистрация: 06.02.2010
Сообщений: 131
|
|
21.11.2010, 14:50 | 10 |
0
|
Почетный модератор
64299 / 47594 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
|
|
21.11.2010, 14:53 | 11 |
Сначала написал, потом заметил, быстро поправил. Можно
const nmax=49999; тогда [1..nmax]; Добавлено через 29 секунд Вообще глупый вопрос, лишь бы что-то вякнуть...
0
|
шарпопочитатель
59 / 26 / 7
Регистрация: 31.01.2010
Сообщений: 1,035
|
|
21.11.2011, 15:41 | 12 |
а в этой задаче можно наоборот узнать с какого человека начинали мы считать?
То есть имея в качестве данных последнее человека.
0
|
Почетный модератор
64299 / 47594 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
|
|
21.11.2011, 15:43 | 13 |
Конкретно в этой нет, а если переделать, да.
0
|
шарпопочитатель
59 / 26 / 7
Регистрация: 31.01.2010
Сообщений: 1,035
|
|
21.11.2011, 15:49 | 14 |
Puporev, а как переделать? Я вот не втыкаю как именно. Смотри, у нас уже все мертвы солдаты например. Остался один. и мы не знаем какой предыдущий был даже. То есть убивать легче чем возрождать)))
Или тут прикол какой то есть? Типо если тот же самый алгоритм запустить с того солдата который выжил, то получим номер того с которого все начиналось?
0
|
Почетный модератор
64299 / 47594 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
|
|
21.11.2011, 16:37 | 15 |
Почему не знаем, он был на К позиций левее...
Добавлено через 43 секунды Какая разница вычеркивать или записывать? Только направление сменилось и все.
0
|
шарпопочитатель
59 / 26 / 7
Регистрация: 31.01.2010
Сообщений: 1,035
|
|
21.11.2011, 18:20 | 16 |
Puporev, если честно не смотрел ваш код пока. Но есть вариант у меня со связными спиками двунаправленными, так вот там элементы удаляются как бы. То есть там на К позиций не вернешся просто так.
0
|
Почетный модератор
64299 / 47594 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
|
|
21.11.2011, 19:10 | 17 |
Так и здесь удаляются. Вам же не нужны все номера, нужно вставлять пока не все и получите номер первого, он же не номер 1 будет.
0
|
13102 / 5883 / 1706
Регистрация: 19.09.2009
Сообщений: 8,808
|
||||||
12.06.2013, 17:33 | 18 | |||||
Здесь, кстати, при решении этой задачи можно использовать расчёт, который обсуждался выше в теме.
Пускай, формулировка задачи будет такой: 3 - 1 = 2 Теперь, зная расстояние, вычисляем номер начального участника для случая, когда остался участник под номером 6: 6 - N = 2 -> N = 6 - 2 = 4 Ответ - если остался участник под номером 6, то, значит, в этом случае, считать начали с участника под номером 4. Теперь выведем формулы с учётом цикличности. Предположим, у нас M участников, мы начали считать с участника под номером N и после счёта остался участник под номером K. Тогда, "расстояние" между участниками N и K равно: D = K - N Отсюда следует, что: N = K - D С учётом цикличности по модулю M получим: N = (M + K - D) mod M Теперь у нас есть формула для определения номера начального участника N, в случае если мы знаем номер последнего оставшегося участника К и расстояние между начальным и конечным участниками D. Номер оставшегося участника К - мы знаем. Осталось определить расстояние D. Для этого делаем следующее, запускаем расчёт номера оставшегося участника при начале счёта N1=1. В результате получим K1. Отсюда вычислим D: D = K1 - N1 Теперь, зная M, K и D получим номер участника с которого начался счёт: N = (M + K - D) mod M Решение будет выглядеть так:
Хоть и археология, но я думаю, может кому-нибудь понадобится решение.
0
|
13 / 13 / 10
Регистрация: 25.05.2015
Сообщений: 554
|
|
01.06.2016, 17:35 | 19 |
Здравствуйте как вывести тех участников которые выбили?
Добавлено через 6 часов 42 минуты lexus_ilia, В вашем коде считалочка неверно идет, она у вас начинает со второго элемента считать
0
|
13102 / 5883 / 1706
Регистрация: 19.09.2009
Сообщений: 8,808
|
||||||
09.06.2016, 08:14 | 20 | |||||
Решение на кольцевом динамическом списке.
Выбывание участников идёт до момента, когда останется только 1 участник. Если количество оставшихся участников нужно сделать другое - для этого надо поменять значение в условии цикла WHILE в 131-й строке кода.
Возможно, у кого-то будут трудности в понимании, как исключаются целые периоды. Тогда можно взять код, в котором целые периоды не исключаются: Определить порядок удаления ребят из круга Там всё правильно считается. Обращу внимание, что lexus_ilia писал код в соответствии с условием задачи из заглавного поста темы. А там было сказано:
0
|
09.06.2016, 08:14 | |
09.06.2016, 08:14 | |
Помогаю со студенческими работами здесь
20
Убрать из массива каждое второе число, пока не останется одно Постоянный выбор второго элемента списка, пока не останется один Считалка: удаление каждого пятого элемента в списке, пока не останется 1 элемент Прогонять массив до тех пор, пока в нем не останется нулевых значений Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |