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

Задача про кузнечиков - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Оптимизация программы http://www.cyberforum.ru/cpp-beginners/thread587463.html
Здравствуйте, получил я задание написать программу перемножения двух больших чисел, используя быстрое преобразование Фурье. Дал мне преподаватель на это 4 дня, чему я очень удивился - маловато будет, да и к тому же зачетная неделя. Ну да ладно, нашел пару статей - худо-бедно написал. Прихожу сегодня сдавать, получаю ответ такой, что мол фуфло все, давай оптимизируй, мол, ускорь процесс. Вобщем...
C++ Разнообраный ввод даты Как устроить разнообразный ввод даты? Например: 03.08.1994 или 3.8.94. Не обязательно через точку, как угодно. http://www.cyberforum.ru/cpp-beginners/thread587461.html
C++ как занести значения в vector из файла и сохранить их в файл?
Требуется написать класс для работы с текстовым файлом - проверка его состояния, позиция курсора, размер и т.д. С горем пополам наваял. Но вот условие задачи: "На основе разработанного класса разработайте приложение, выполняющее считывание входного текстового файла в память (для выделения массива данных нужного размера используйте класс vector), реверсирование массива символов, считанных из...
C++ Оптимизация программы
Извиняюсь, тема создана ошибочно, прошу модератора удалить
C++ задание по курсовой.в с++ особо не соображаю. исправьте пожалуйста ошибки,хотя бы те,которые видимы сразу http://www.cyberforum.ru/cpp-beginners/thread587454.html
void __fastcall TForm5::Button4Click(TObject *Sender) { int min,i,kfor,n; file f1; char *s; f1=fopen("Temp","wt"); n=Memo1->Lines->Count-1; for (i=0;i< n;i++) { s=Memo1->Lines->Strings.c_str;
C++ Поразрядная сортировка чисел со знаком Уважаемые, будьте добры помочь с задачей, в которой нужно реализовать поразрядную сортировку чисел со знаком под консоль. Если это очень трудоемко, то подскажите сам алгоритм. Заранее благодарен! подробнее

Показать сообщение отдельно
33parrots
3 / 3 / 0
Регистрация: 25.05.2012
Сообщений: 23
26.05.2012, 18:47     Задача про кузнечиков
будем обозначать к-во вариантов с позиции, когда осталось Р столбиков f(p). Тогда
f(p)= f(p-1) + f(p-2) + ... + f(p-k),
причём f(0)=1, f(число меньше 0)=0.

И если впадло писать код и n маленькое - пошла рекурсия,
если хочешь нормально - создаём массив размером n, в котором будут храниться f(p) для р=1..n
И пошла индукция, р увеличивем от 1 до n, на каждом шаге сохраняем f(p) в массив. Этот алгоритм требует n раз взять сумму k (по крайней мере не более чем k) элементов, но подлость в том, что такой алгоритм не оптимален.

Ведь на самом деле
f(p) = f(p-1) + f(p-2) + ... + f(p-k) = f(p-1) + f(p-1) - f(p-k-1) = 2*f(p-1) - f(p-k-1)
И тогда для нохождения каждого нового элемента нам нужно 2 операции сложения вместо к операций сложения. Можно заюзать операцию умножения и операцию сложения, здесь вопрос в том, что легче - (операция умножения) или (операция сложения плюс дополнительное обращение к ячейке памяти). Я начинающий программист, на такой вопрос ответа, к сожалению, не знаю.

Итого имеем 2n операций сложения + 3n обращений к ячейкам, либо n операций сложения, столько же операций умножения и 2n обращений к ячейкам. Довольно похоже на оптимальныое решение.
 
Текущее время: 02:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru