Страница 1 из 1
разминочная задачка .. разговор поддержать :)
Добавлено: 22 фев 2003, 14:48
ajkj3em
Рассматривается упорядоченная по возрастанию последовательность чисел вида 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 сек.
Добавлено: 23 фев 2003, 17:50
Boo
Я не знаю как с ХТ-шкой сравнивать. Вот такой солюшн у меня мгновенно выдает результат и для 1000, и для 1500:
Код: Выделить всё
#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 ) ) ) ;
}
где-то в районе 1690 кончаются разряды...
. Вроде потребляемая память и скорость растут линейно (ну или почти линейно), если я ничего не путаю. В таком вот аксепте....
Добавлено: 23 фев 2003, 17:54
Boo
Во времена ХТ-шек STL-а не было еще
Добавлено: 23 фев 2003, 19:54
ajkj3em
Boo писал(а):Я не знаю как с ХТ-шкой сравнивать. Вот такой солюшн у меня мгновенно выдает результат и для 1000, и для 1500:
Код: Выделить всё
#include <stdio.h>
#include <string.h>
.. snip..
где-то в районе 1690 кончаются разряды... :( . Вроде потребляемая память и скорость растут линейно (ну или почти линейно), если я ничего не путаю. В таком вот аксепте....
круто :)
ни точный ответ, ни сам алгоритм я честно говоря не помню, но идея - схожая, то есть переход к следующему числу по уже имеющимся.