Рассматривается упорядоченная по возрастанию последовательность чисел вида 2^a * 3^b * 5^c, где a,b,c >=0. Начало последовательности очевидно 1,2,3,4,5,6,8,9,10,12,15. Предложить алгоритм нахождения n-го числа, отличный от простого перебора.
Hint: во времена XT-шек n было в районе 1000, так что тупой перебор занимал несколько часов, когда одно из решений отрабатывало за 30 сек.
разминочная задачка .. разговор поддержать :)
Правила форума
Пожалуйста, ознакомьтесь с правилами данного форума
Пожалуйста, ознакомьтесь с правилами данного форума
- ajkj3em
- Маньяк
- Сообщения: 2063
- Зарегистрирован: 12 ноя 2006, 06:53
-
- Пользователь
- Сообщения: 92
- Зарегистрирован: 20 фев 2003, 00:41
Я не знаю как с ХТ-шкой сравнивать. Вот такой солюшн у меня мгновенно выдает результат и для 1000, и для 1500:
где-то в районе 1690 кончаются разряды... . Вроде потребляемая память и скорость растут линейно (ну или почти линейно), если я ничего не путаю. В таком вот аксепте....
Код: Выделить всё
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std ;
int gen235( int nMax )
{
vector<int> v ;
int ii[3], nv[3], n[3] ;
v.resize( nMax ) ;
v[0] = 1 ;
fill( ii, ii + 3, 0 ) ;
n[0] = 2 ; n[1] = 3 ; n[2] = 5 ;
copy( n, n + 3, nv ) ;
for( int i = 1 ; i < nMax ; i += ( ( v[i] == v[i-1] ) ? 0 : 1 ) )
{
int jMin = min_element( nv, nv + 3 ) - nv ;
v[i] = nv[ jMin ] ;
nv[jMin] = v[ ++(ii[jMin]) ] * n[jMin] ;
}
return v.back() ;
}
void main( int argc, char* argv[] )
{
printf( "gen235: %d\n", gen235( strtol( argv[1], 0, 10 ) ) ) ;
}
-
- Пользователь
- Сообщения: 92
- Зарегистрирован: 20 фев 2003, 00:41
- ajkj3em
- Маньяк
- Сообщения: 2063
- Зарегистрирован: 12 ноя 2006, 06:53
круто :)Boo писал(а):Я не знаю как с ХТ-шкой сравнивать. Вот такой солюшн у меня мгновенно выдает результат и для 1000, и для 1500:
где-то в районе 1690 кончаются разряды... :( . Вроде потребляемая память и скорость растут линейно (ну или почти линейно), если я ничего не путаю. В таком вот аксепте....Код: Выделить всё
#include <stdio.h> #include <string.h> .. snip..
ни точный ответ, ни сам алгоритм я честно говоря не помню, но идея - схожая, то есть переход к следующему числу по уже имеющимся.