Новости
Видео
Microsoft
Windows 10
Железо
Программы
Форум

Имя пользователя:
Пароль:  
Помощь | Регистрация | Забыли пароль?  | Правила  

Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » C/C++ - Ускорение поиска числа факториала

< Предыдущая 1 2 3 4 Следующая >
Ответить
Настройки темы
C/C++ - Ускорение поиска числа факториала

Старожил


Сообщения: 222
Благодарности: 1

Профиль | Отправить PM | Цитировать

Люди помогите сделать бысрый алгоритм нахождения числа из его факториала.
Я писал вот такой код но он оч медленный
Код: Выделить весь код
#include <iostream.h>
#include <fstream.h>
int faknom(int a)
{
	int i=1;
	while(a!=i)
	{
		a=a/i;
		i++;
	};
	return i;
};
int main()
{
	int Nfak;
	ifstream fin("input.txt");
	fin>>Nfak;
	fin.close();
	ofstream fout("output.txt");
	fout<<faknom(Nfak)<<endl;
	fout.close();
	return 0;
}
В файле input.txt лежит значение факториала N! числа N, а в файле output.txt должно быть записано значение N.
Как ускорить алгоритм расчета?

Отправлено: 13:00, 01-06-2008

 

редкий гость


Сообщения: 1696
Благодарности: 44

Профиль | Сайт | Отправить PM | Цитировать

Такой, который использует длинную арифметику. Лучше не a делить на i, а ввести некоторое b, которое домножать на i до тех пор пока b < a. (потому что умножение длинных чисел сильно быстрее деления)

-------
http://ivank.ru

Отправлено: 14:47, 01-06-2008 | #11



Для отключения данного рекламного блока вам необходимо зарегистрироваться или войти с учетной записью социальной сети.

Если же вы забыли свой пароль на форуме, то воспользуйтесь данной ссылкой для восстановления пароля.


Старожил


Сообщения: 222
Благодарности: 1

Профиль | Отправить PM | Цитировать

Всеравно исчерпывается лимит времени.
Тут полный проход по деления или умножению некатит. Над
какойто иной способ.
А на ассемблере что никто и нескажет как написать?

-------
Подпись, нарушающая правила конференции, отредактирована администратором

Отправлено: 15:06, 01-06-2008 | #12


Аватара для Altair86

Новый участник


Сообщения: 15
Благодарности: 2

Профиль | Отправить PM | Цитировать

А для чисел меньше 12 за сколько времени прога срабатывает?

-------
Будь проклят тот день, когда обезьяна слезла с дерева и научилась говорить...

Отправлено: 15:21, 01-06-2008 | #13


Ветеран


Сообщения: 3320
Благодарности: 916

Профиль | Отправить PM | Цитировать

На ассемблере (как и в Паскале и в С) есть так называемые операции сдвига:
вправо (shr) и влево (shl). Для десятичной системы это выглядит так
Код: Выделить весь код
3 shl 5 => (3x(2в пятой степени))
5 shr 3 =>(5/(2в третей степени))
На примере двоичной системе становится ясно откуда они получили своё имя
00010101 shl 3 => 10101000
и в другую сторону при shr
Они могут быть полезны, если придумать как их здесь можно применить.

Отправлено: 15:33, 01-06-2008 | #14


Старожил


Сообщения: 222
Благодарности: 1

Профиль | Отправить PM | Цитировать

Че придумывать если я ассемблера незнаю?

-------
Подпись, нарушающая правила конференции, отредактирована администратором

Отправлено: 16:09, 01-06-2008 | #15


Ветеран


Сообщения: 1404
Благодарности: 135

Профиль | Отправить PM | Цитировать

Почему бы не создать список всех факториалов до 2000 в файле!?

номер факториала соответствует номеру строки.
Считываем заданное число, помещаем в строку, определяем длину строки

и начинаем сравнивать длину строки заданного числа с длинами строк в файле,
Начать нужно не с нуля, а со строки номер которой равен длине строки заданного числа.

Если длины строки равны, то номер строки в файле искомый факториал.

Таким образом задача избавляется от чрезмерно быстрого факториального роста. задача сводится к поиску. Можно создать 2000 файлов, чтобы не мучать один файл и сравнивать уже количество байт файла в котором заданное число и количество байт в файле, в котором факториалы. Просто тупо проверяем есть ли файл заданного размера. Без вычислений.

-------
Ehhh.. what's up, doc?..

Последний раз редактировалось mrcnn, 01-06-2008 в 16:27.

Отправлено: 16:13, 01-06-2008 | #16


Старожил


Сообщения: 222
Благодарности: 1

Профиль | Отправить PM | Цитировать

Понимаете ето задача для онлайн контестера тип АСМ. Время выполнения программы для даной задачи ограничено 1 секундой и обьем кода до 4кб. И кроме кода сторонних фаилов использовать нельзя.

-------
Подпись, нарушающая правила конференции, отредактирована администратором

Отправлено: 16:24, 01-06-2008 | #17


Ветеран


Сообщения: 3320
Благодарности: 916

Профиль | Отправить PM | Цитировать

DaRiYs, я указал что
Цитата Admiral:
как и в Паскале и в С »
во вторых я показал математику этого оператора
Цитата Admiral:
Код: Выделить весь код
3 shl 5 => (3x(2в пятой степени))
5 shr 3 =>(5/(2в третей степени))
»
Я оператор с ассемблером связал, так как при изучении его с ним познакомился, а потом обнаружил его в С и Паскале. (вернее в С я про него узнал, но природу процесса понял при изучении ассемблера).

Отправлено: 16:28, 01-06-2008 | #18


Ветеран


Сообщения: 1404
Благодарности: 135

Профиль | Отправить PM | Цитировать

Надо было сразу указывать эти ограничения. Что такое контестер, что такое ACM и что такое контестер типра ACM?

-------
Ehhh.. what's up, doc?..

Отправлено: 16:38, 01-06-2008 | #19


Аватара для Drongo

Будем жить, Маэстро...


Сообщения: 6694
Благодарности: 1393

Профиль | Сайт | Отправить PM | Цитировать

Coutty,
Цитата Coutty:
Drongo, перед выполняемой функцией определяешь системное время с точностью до миллисекунд »
Если честно, то я не знаю, как его определять?! Можно на примере или прочесть где?! Чтобы доходчиво было.

-------
Правильная постановка вопроса свидетельствует о некотором знакомстве с делом.
3нание бывает двух видов. Мы сами знаем предмет — или же знаем, где найти о нём сведения.
[Quick Killer 3.0 Final [OSZone.net]] | [Quick Killer 3.0 Final [SafeZone.cc]] | [Парсер логов Gmer] | [Парсер логов AVZ]

http://tools.oszone.net/Drongo/Userbar/SafeZone_cc.gif

Отправлено: 16:40, 01-06-2008 | #20

< Предыдущая 1 2 3 4 Следующая >


Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » C/C++ - Ускорение поиска числа факториала

Участник сейчас на форуме Участник сейчас на форуме Участник вне форума Участник вне форума Автор темы Автор темы Шапка темы Сообщение прикреплено

Похожие темы
Название темы Автор Информация о форуме Ответов Последнее сообщение
Простые числа на Си++ nemo555 Программирование и базы данных 13 13-03-2007 21:24
*Теория* | Числа Фибоначчи Grub Программирование и базы данных 8 28-07-2006 14:23
четность числа elfoflorien Вебмастеру 6 18-09-2005 20:49
Случайные числа на JavaScript Dimonweb Вебмастеру 2 12-08-2004 03:23
суммироват числа Artashes Программирование и базы данных 3 30-08-2003 18:31


« Предыдущая тема | Следующая тема »


 
Переход