|
|
|
|
|
|
|
Вернуться
| 1 Присяжнюк Анатолий Васильевич, 03 сентября 2009 г. 20:46:45 | |
Решаема, только смотря каким алгоритмом :)
Вообще, эта задача в классной редакции (нужно поискать исходник условия у меня в архиве - руки не доходят из-за нехватки времени :) ) была в свое время на прекрасном белорусском проекте ttb.by, к сожалению, почему-то закрытом.
Кто желает порешать эту задачу для больших значений, смотрите, например, задачку http://acm.pku.edu.cn/JudgeOnline/problem?id=2939 - там ограничения довольно большие (условие - на английском, ввод-вывод - консольный).
В классике эта задача встречается в разных вариантах и является классической и очень полезной с точки зрения постоянного поиска путей оптимизации алгоритмического решения для заданных в конкретной задаче ограничений или нюансов.
Предложение к Админу - может подумать о тематической олимпиаде на эту тему?
Если нужно - готов помочь.
|
|
|
| 2 Нагин Сергей Юьевич, 03 сентября 2009 г. 14:42:55 | |
|
для М=2 , она решаема и для 1000000000!)
|
|
|
| 3 Прищенко Богдан Олегович, 03 сентября 2009 г. 0:13:50 | |
|
Спасибо:)
|
|
|
| 4 Присяжнюк Анатолий Васильевич, 03 сентября 2009 г. 0:08:34 | |
|
На украинском портале дистанционного обучения (Винница - Пасихов Ю.Я. - http://disted.edu.vn.ua/ ) есть разбор этой задачи (жаль, что только на украинском языке).
|
|
|
| 5 Прищенко Богдан Олегович, 02 сентября 2009 г. 22:05:33 | |
|
Погуглил, ознакомился с темой... Код на паскале - лобовик, его в топку... На с++ - более-менее нормальное решение. При больших ен задача толком не решается, если ем тоже достаточно большое... там, где я ее видел с ограничением 100000000 действительно было довольно маленькое ем, при большом шаге щиталки она, если верить инфе с сети, неразрешима в пределах нескольких секунд.
|
|
|
| 6 Мехрдоди Одил (ТРГИ), 02 сентября 2009 г. 21:35:16 | |
Прищенко Богдан Олегович, 02 сентября 2009 г. 20:47:26
в его решении на с++, КАК РАЗ и ИСПОЛЬЗУЕТСЯ СТАНДАРТНАЯ ФОРМУЛА.
|
|
|
| 7 Прищенко Богдан Олегович, 02 сентября 2009 г. 20:56:44 | |
в украинской википедии в статье о задаче есть формулы, кому надо - смотрите.
|
|
|
| 8 Прищенко Богдан Олегович, 02 сентября 2009 г. 20:51:39 | |
|
Ага, отгуглил. Решение с вики для ограничений 500. Для больших формула есть в сети, искать надо, я пока этого еще не осваивал, руки не дошли, всегда надеюсь не нарваться на эту задачу:)
|
|
|
| 9 SKYDOS, 02 сентября 2009 г. 20:49:23 | |
Прищенко Богдан Олегович, 02 сентября 2009 г. 20:47:26
здесь типа написано "Взято с википедии"...))) код не мой сразу говорю)
|
|
|
| 10 Прищенко Богдан Олегович, 02 сентября 2009 г. 20:47:26 | |
|
SKYDOS, а что здесь вообще написано? Я вижу только убийственное решение лобовиком:) Акашаев, при н=10000 должен и лобовик проходить. А при полноценных ограничениях, например, 10 миллионов, или же при обратной "переборной" задаче никакой оптимайз лобовика не спасет. Надо просто юзать стандартную формулу.
|
|
|
| 11 Акашаев Нурлан Амангельдиевич, 02 сентября 2009 г. 19:57:46 | |
|
Спасибо!
|
|
|
| 12 SKYDOS, 02 сентября 2009 г. 19:39:24 | |
С++
int joseph (int n, int k) {
return n ? (joseph (n-1, k) + k - 1) % n + 1 : 1;
}
Паскаль
program TheJosephusProblem;
uses
SysUtils;
const nmax=500;
var mass:array[1..nmax] of integer;
i,j,m,n: integer;
begin
read(n,m);
for i:=1 to n do
mass[i]:=i;
i:=1;
while n>1 do begin
i:=(i+m-1) mod n;
if i=0 then i:=n;
for j:=i to n-1 do
mass[j]:=mass[j+1];
n:=n-1;
end;
writeln(mass[1]);
end.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
