Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Задачи для тренировки и лучшего понимания - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Возможно переписать программу? http://www.cyberforum.ru/cpp/thread153534.html
Есть программа Upgrade UA.exe хочу запустить ее на windows mobile 6. Возможно ли ее переписать.
C++ scanf Пусть нужно читать из текста слова, пропуская все символы, кроме a-z и A-Z. То есть из текста Hello, world! ololo O_o получить только Hello world ololo O o Меня интересует, можно ли это... http://www.cyberforum.ru/cpp/thread153153.html
C++ Вернуть stdin в консоль
Допустим я перенаправил поток stdin/stdout в файл с помощью функции freopen. Как заставить его снова работать с консолью? Добавлено через 9 минут Нашел. #include <cstdlib> #include <stdio.h>...
Прошу помочь.Подключение dll на неуправляемом С/С++ C++
Возникла проблема.Есть рабочая dll, необходимо подключить к CLR приложению. Подключение происходит нормально. Все функции работают нормально кроме одной(хотя dll проверял все работает в обычных...
C++ Не сразу закрывающаяся программа http://www.cyberforum.ru/cpp/thread152799.html
Есть команды в терминале.. вроде telnet или sql, эти программы запускаешь и они остаются открытыми пока не дашь команду, например, quit. Во время работы программы она показывает знак приглашения...
C++ Парсер на С вопшем есть файл с текстом..... в етом файле есть какие даные(мусор)...и есть дни: Понедельник,Вторник,среда......с етого файла нада вывести ети дни в порядке нахождениэ... ето походу несложная... подробнее

Показать сообщение отдельно
nikkka
Мат в 32 хода
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
28.07.2010, 13:59
Вот мат. часть задачки.
Цитата Сообщение от Aye Aye Посмотреть сообщение
привести математические обоснования
На данный момент я займусь изложением придуманной теории: как найти мин. количество ходов. Сначала я просто попробовал подсчитать, сколько нужно ходов для разных n. Вот что у меня получилось (n кол. "кружочков", k кол. ходов):
Код
n=1, k=2;
n=2, k=8;
n=3, k=26;
n=4, k=80;
По моему этого достаточно что бы заметить что новый k выражается по формуле 3(предыдущий k)+2. А теперь то что я "заметил", надо доказать. Итак. Допусти мы знаем, что для некого кол. "кружочков" n, есть мин. кол. ходов k. Каким оно будет для n+1? Начнем рассуждать. Что бы перенести (n+1)-ый кружочек с палочки А на палочку С, мы должны "преодолеть" палочку В. Для этого, мы должны перенести все остальные кружочки на палочку С, МИНИМАЛЬНЫМ количеством ходов. А оно (по условию) k. Итак, теперь мы знаем, что для n+1 кружочков, мин. кол. ходов для (n+1) кружочков будет k+... (дальше узнаем, чему равны эти "..."). Что мы имеем? Пирамидку из n кружочков на палочке С и (n+1)-ый кружочек на палочке А. Переносим его на палочку В. Теперь кол. мин. ходов для (n+1) кружочков = k+1+... . Далее, мы должны перенести (n+1)-ый кружочек на палочку С, для чего должны сначала освободить ее. Переносим пирамидку из n кружочков на палочку А, МИНИМАЛЬНЫМ кол. ходов. Мы знаем что оно = k. Теперь мин. кол. ходов для (n+1) кружочков = k+1+k... . Теперь, когда палочка С свободна, переносим на нее (n+1)-ный кружочек. Это уже k+1+k+1 ходов. А теперь перенесем пирамидку с А на С, где лежит наш (n+1)-ный кружок. А это уже k+1+k+1+k= 3k+2. А реализовать это рекурсией не сложно. Чем я сейчас и займусь...
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru