разминочная задачка .. разговор поддержать :)

[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 сек.

[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 кончаются разряды... . Вроде потребляемая память и скорость растут линейно (ну или почти линейно), если я ничего не путаю. В таком вот аксепте....

[Boo]

Во времена ХТ-шек STL-а не было еще

[ajkj3em]

Я не знаю как с ХТ-шкой сравнивать. Вот такой солюшн у меня мгновенно выдает результат и для 1000, и для 1500:

Код: Выделить всё

#include <stdio.h>
#include <string.h>

.. snip..

где-то в районе 1690 кончаются разряды... :( . Вроде потребляемая память и скорость растут линейно (ну или почти линейно), если я ничего не путаю. В таком вот аксепте....

круто :)

ни точный ответ, ни сам алгоритм я честно говоря не помню, но идея - схожая, то есть переход к следующему числу по уже имеющимся.