15.07.2010, 05:53 | |
Ответы с готовыми решениями:
1272
Элементарные программы, для лучшего понимания языка... Задачи для тренировки и лучшего понимания языка Литература для лучшего понимания сути программирования Набор задачь для тренировки и улучшения понимания программирования |
1552 / 918 / 193
Регистрация: 26.03.2010
Сообщений: 3,105
|
|
17.08.2010, 22:06 | 721 |
0
|
18.08.2010, 11:48 | 722 |
Не давала она мне покоя, решил попробовать написать.
Пока был в отпуске тема разраслась до внушительных размеров, поэтому не знаю - решил ли ее кто -нибудь, а все перечитывать лень) Вобщем вот, голову пришлось поломать) Начнем с того, что нужно просчитать 63 хода, конь потенциально имеет 8 ходов(вверх влево, вверх вправо и т.д.) таким образом нужно просчитать 8^63=много милиардов возможных ходов. (по крайней мере я подошел к решению этой задачи именно так)) Написал код, потом всеми доступными силами его оптимизировал (на сколько знаний хватило)). Результат - первые 12 ходов просчитывает достаточно быстро, 13ый ход уже подольше, 14ый около 30-40 минут, оставил программу работать на ночь) Утром (точнее в обед) проснулся, посмотрел сколько просчитала - 15(!) ходов всего! По самым скромным подсчетам на готовое решение уйдет несколько лет! nikkka, вы где эту задачу взяли? Мне кажется как не крути, а быстрого решения нет! Могу ошибаться, поэтому хотелось бы услышать ваши коментарии по поводу этой задачи и, если в теме есть ее решение, дайте знать. Не по теме: Дома инет в блоке, пишу с чужого компа, кода по рукой нет, поэтому выложить его не могу. К сожалению ваши ответы прочитаю через несколько дней, когда денег на инет кину))
0
|
Мат в 32 хода
237 / 172 / 18
Регистрация: 10.09.2009
Сообщений: 1,096
|
|
18.08.2010, 12:02 | 723 |
Балада о нерешённой задачке, или как Kastaneda не дал себе покоя.
Об этой задачке мне впервые рассказал учитель информатики, когда я был в седьмом классе. Тогда программированием я не увлекался, так что не обратил внимания. Учитель сказал что это была его первая серьёзная решённая задачка. Позже, я всречал её на многих сайтах, но даже и не думал решать. Вообще то попробовал один раз, но ничего хорошого с этого не вышло . Не согласен. Число будет НАМНООООООООГО меньше. У 63-его хода, вообще будет один а не восемь вариантов. Ещё к примеру когда конь стоит на крайней клетке (к слову на А5), число возможных ходов будет 4, а не 8. К тому же, откуда в знаете что все 8 (или 4) клеток не были пройдены? 8^63 неверное число. Задача на форуме ещё не решалась, но лично мне будет интересно посмотреть на код. Оно есть.
0
|
4342 / 1474 / 680
Регистрация: 12.03.2009
Сообщений: 5,310
|
|
18.08.2010, 12:09 | 724 |
nikkka, раз пошёл разговор о шахматах, то есть ещё одна классическая задача (скорее всего, её тоже обсуждали)
На шахматной доске N*N требуется расставить N ферзей таким образом, чтобы ни один ферзь не атаковал другого.
0
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
|
18.08.2010, 12:15 [ТС] | 725 |
k1ry4, Обычно 8 ферзей. Так она и называется. Вроде бы где-то тут была
0
|
18.08.2010, 12:15 | 726 |
С таким подходом придется писать несколко ф-ций для проверки наличия хода под разные положения коня на шахмотной доске и в зависимости от него(положения) вызывать ту или иную ф-цию. Я же написал одну универсальную, которая проверяет все 8 ходов.
0
|
4342 / 1474 / 680
Регистрация: 12.03.2009
Сообщений: 5,310
|
|
18.08.2010, 12:17 | 727 |
Lavroff, ну да, чаще всего дают разобрать частный случай N = 8. Но общий случай ещё никто не решал
0
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
|
18.08.2010, 12:20 [ТС] | 728 |
k1ry4, Ну. Общий случай это как минимум жестоко)
Не по теме: Ты в С++ перешел?)
0
|
4342 / 1474 / 680
Регистрация: 12.03.2009
Сообщений: 5,310
|
|
18.08.2010, 12:26 | 729 |
Lavroff, ну даже частный для N >= 11 уже слишком
Не по теме: Потихоньку, полегоньку
0
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
|
18.08.2010, 12:36 [ТС] | 730 |
k1ry4, Я почему-то не могу представить шахматную доску более чем 8 на 8... А что есть еще по шахматам?
0
|
4342 / 1474 / 680
Регистрация: 12.03.2009
Сообщений: 5,310
|
|
18.08.2010, 12:47 | 731 |
Lavroff, есть ещё одна (подскажу, что тема - графы)
На телефонном аппарате имеется десять кнопок, расположенных следующим образом: [1][2][3] [4][5][6] [7][8][9] ... [0] ... Конь может стартовать с любой кнопки и передвигаться на следующую только Г-образным ходом (т.е. с кнопки 1 он может попасть либо на 6, либо на 8). Сколько различных N-значных номеров можно набрать таким образом? Всё зависит от конфигурации поля, можно придумать поизощрённее.
2
|
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
|
||||||
18.08.2010, 20:11 | 732 | |||||
Наверное как-то так
0
|
Мат в 32 хода
237 / 172 / 18
Регистрация: 10.09.2009
Сообщений: 1,096
|
|
18.08.2010, 20:26 | 733 |
k1ry4, разве это как ни будь связанно с программированием?
0
|
Временно недоступен
957 / 228 / 14
Регистрация: 12.04.2009
Сообщений: 926
|
|
18.08.2010, 22:22 | 734 |
Наверняка кто-то уже решил,ну не бывает так)
Скорее всего,у этой задачи есть математическое решение с использованием системы координат на плоскости (если речь шла про ферзей).
1
|
4342 / 1474 / 680
Регистрация: 12.03.2009
Сообщений: 5,310
|
|
18.08.2010, 22:39 | 735 |
0
|
Мат в 32 хода
237 / 172 / 18
Регистрация: 10.09.2009
Сообщений: 1,096
|
|
18.08.2010, 23:10 | 736 |
k1ry4, этож чисто мат. задачка. нужна расчётная формула, и только. нас же не просят вывести эти номера...
0
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
||||||
21.08.2010, 22:47 [ТС] | 737 | |||||
Числа Падавана (или как-то так), вчера ночью нашел. Интересная вещь. Похожи на Фибоначчи. Так вот. Хотелось бы увидеть решение итеративным методом. Рекурсивным делается элементарно, а вот насчет итеративного - хз. Рекурсивное решение внизу. Два варианта разного написания, алгоритм одинаковый.
0
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
22.08.2010, 02:09 | 738 |
Lavroff,
А у неё точно есть итеративное решение? А то я тут порасписывал для разных чисел - как-то неоднозначно получается, не видно явного алгоритма... Просто в тех же числах Фибоначчи на каждом следующем шаге обязательно используется результат предыдущего (на то метод и итеративный), а здесь результат n-той итерации может потребоваться только ещё через m итераций... Потому без массива для хранения результатов всех предыдущих итераций, думаю, не обойтись... Но тогда теряется вся прелесть итеративного метода, и находится не n-тое число, а все до n включительно...
1
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
|
22.08.2010, 02:26 [ТС] | 739 |
silent_1991, Вот и хочу узнать возможно это или нет. Потому что сам вчера пытался что-то придумать - не вышло
0
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
||||||
22.08.2010, 03:04 | 740 | |||||
Lavroff,
Вроде напал на след... Сейчас попытаюсь найти закономерность... Добавлено через 32 минуты
Как видно, приходится за одну итерацию вычислять сразу два очередных числа - чётное и нечётное, т.к. каждое k-е число потребуется для вычисления только (k+2)-го и (k+3)-го чисел...
1
|
22.08.2010, 03:04 | |
22.08.2010, 03:04 | |
Помогаю со студенческими работами здесь
740
Проверить на правильность и закомментировать весь код для лучшего понимания Нужны задачи для тренировки Нужны задачи для тренировки Нужны задачи для тренировки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |