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

Все, что вы хотели знать о программизме, но боялись спросить.
Аватара пользователя
ajkj3em
Маньяк
Сообщения: 2063
Зарегистрирован: 12 ноя 2006, 06:53

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

Сообщение ajkj3em » 22 фев 2003, 14:48

Рассматривается упорядоченная по возрастанию последовательность чисел вида 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
Пользователь
Сообщения: 92
Зарегистрирован: 20 фев 2003, 00:41

Сообщение Boo » 23 фев 2003, 17:50

Я не знаю как с ХТ-шкой сравнивать. Вот такой солюшн у меня мгновенно выдает результат и для 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
Пользователь
Сообщения: 92
Зарегистрирован: 20 фев 2003, 00:41

Сообщение Boo » 23 фев 2003, 17:54

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

Аватара пользователя
ajkj3em
Маньяк
Сообщения: 2063
Зарегистрирован: 12 ноя 2006, 06:53

Сообщение ajkj3em » 23 фев 2003, 19:54

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

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

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

.. snip..



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


круто :)

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


Вернуться в «Программизм»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 3 гостя