Снова здравствуйте 
Нужно напечатать 1000 неповторяющихся чисел в порядке возрастания из множества M:
1. единица принадлежит к множеству M
2. к множеству M принадлежит число 2*x+1 (х - принадлежит множеству М)
3. к множеству М принадлежит число 3*х+1 (х - принадлежит множеству М)
Конечно можно просто посчитать все, отсортировать и вычеркнуть одинаковые и если не достаточно чисел - повторить процесс, но может можно как-то легче?

Чего-то в Вашем условии явно не хватает. В его рамках ряд чисел a(n)=2*a(n-1)+1, a(0)=1 будет ответом, но, наверное, хочется получить что-то другое?

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

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

А вообще чего-то я не улавливаю числа отличного от 0, в котором бы эти функции дали одинаковый результат... учитывая что это уравнение двух прямых...

Чисто как вариант я бы попробовал бы на бумаге вычислить закономерность для общего рада... мне кажется она будет и тогда решение станет ещё элегантнее, но в лоб мне такое например не далось...а может я ошибаюсь...

А вообще просто обратите внимание на то что у вас два ряда и у одного коэффициент больше, это значит что все его значения всегда будут больше, и значит его надо вычислять всегда вторым и следовательно не будет нужды в сортировке.
Т.е. нм мой взгляд нечто такое
1) 1 подставляет в 1-ю ф-цию, потом во вторую
2) полученный результат по очередно в первую функцию, потом во вторую.
3) результат предыдущего шага опять же в 1-ю функцию, потом во вторую.

Обратите внимание на то как растёт последовательность в плане количества членов и можно будет точно отсчитать момент останова по количеству новых членов, не считая полного количества элементов.

Добавлено через 2 минуты и 51 секунду

Эмм, а тут точно нет ошибки, на первом шаге должно получиться 2 числа - 3 и 4?

Зависимости рекуррентные, так что это не две прямые. К тому же, насколько я понимаю, никак не возбраняется "переключаться" с одной зависимости на другую.

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

да. я написал в порядке возрастания. можно с любого элемента начинать, просто проше всего начинать с 1.
Ряд сначала получается 1 3 4 7 9 10... Тоесть мы получаем из 1 элемента - 2.  
Но если сначала считать первую формулу для 3 а потом для 4 (на первом просчете) а потом второую формулу для них - мы не получим упорядоенный ряд. (реализация на работе, завтра отправлю первые .... много чисел из этого ряда).
Если на некотором просчете мы получили N чисел из которых мы должны получить 2*N (по двум формулам), то в 2*N числах могут быть такие, которые меньше чем числа из N.
Что-то витьевато выражаюсь, за что извиняюсь  

Мое первое "решение" тоже будет выдавать числа в порядке возрастания.   

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

Выглядеть это будет примерно так (поскольку я не знаю, на каком языке это нужно реализовывать, написал на Паскале, для описания алгоритма это проще)

Здесь n - счетчик накопившегося количества чисел, размер 10000 взят "с запасом", чтобы наверняка хватило.

Akina, Вы не правы. Ваш алгоритм не просчитываем числа из множества.
Ряд такой получается:

по вашему алгоритму

dershokus, само собой, я же не учитываю ветвления.
Но идея может быть использована. Правда, потребуется не два аккумулятора, а динамически расширяемый массив аккумуляторов. Из которого берётся наименьший элемент, печатается, затем на его основе генерится и помещается в массив 2 новых значения, а обработанное значение выбрасывается.

Это сообщение отредактировал(а) Akina - 13.11.2012, 10:59

Простейший вариант - взять очередь с приоритетами, в две минуты пишется код:


Ну а если еще чуть подумать, то становится ясно, что это стрельба по воробьям из пушки, и гораздо проще идея, предложенная Фантомом, сделать простой перебор:


Я бы стал сдавать код №2 - проще, быстрее, никакого расхода памяти

Вы забыли одну важную деталь (учет которой, собственно, и приводит к расходу памяти): по условию, числа 2*x+1 и 3*x+1 принадлежат M в том случае, если x принадлежит M (а не является целым числом, как у Вас). Первое отличие - число 5. Оно, конечно, нечетное, но подходящего для него x не существует.

К тому же Ваш вариант (если уж пользоваться измененным условием задачи) можно сильно упростить. Наименьшее общее кратное 2 и 3 равно 6, поэтому код

будет выдавать такой же результат.   

Каюсь, со вариантом №2 просчитался - слишком поверхностно посмотрел Ваш код. Тем не менее, у меня еще есть второй вариант, который №1 

Это да, но всерьез пользоваться возможностями C++, если явно не оговорено, что это можно, как-то нехорошо.   Я сначала тоже успел подумать, что мне больше нравится для этой задачи, Lua или Prolog, и только потом решил, что ТС я этим никак не помогу, после чего сменил язык на наиболее банальный.

http://codepad.org/FKQFn95I

Добавлено через 5 минут и 35 секунд
без повторов же надо.

это без повторов.

Добавлено через 11 минут и 58 секунд


оу, сорри.
паскакалей не знаем.

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