Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Вычисление ряда уникальных чисел по формулам

Автор: dershokus 12.11.2012, 17:29

Снова здравствуйте smile

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

Автор: Фантом 12.11.2012, 19:12

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

Автор: DarkProg 12.11.2012, 19:30

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

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

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

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

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

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

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

Цитата(Фантом @ 12.11.2012, 20:12

)

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

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

Автор: Фантом 12.11.2012, 19:35

Цитата(DarkProg @ 12.11.2012, 20:30

)

учитывая что это уравнение двух прямых...

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

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

Автор: dershokus 12.11.2012, 20:58

Цитата

надо напечатать 1000 наименьших неповторяющихся чисел

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

Автор: Akina 12.11.2012, 21:46

Код


X=1;
Y=X;
Z=0;
Понеслася
  Если X>Y
    Печатаем Y;
    Y=Y*3+1;
  А если X<Y
    Печатаем X;
    X=X*2+1;
  Иначе
    Печатаем Y;
    Y=Y*3+1;
    X=X*2+1;
  Закончили с Если;
  Z=Z+1;
Хреначим пока Z<1000;
Всё собсно.

Автор: Фантом 12.11.2012, 21:53

Цитата(dershokus @ 12.11.2012, 21:58

)

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

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

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

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

Код


program e2x3x;
  var 
  A : array[1..10000] of boolean;
  i,n : integer;
        
  begin
    
    A[1]:=true;
    writeln(1);
    n:=1;
        
    for i:=2 to 10000 do  begin
        A[i]:=(((i-1) mod 3 =0) and A[(i-1) div 3]) or (((i-1) mod 2 =0) and A[(i-1) div 2]);
        if A[i] then begin
          writeln(i);
          inc(n)
        end;    
        if n=1000 then break
    end
end.

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

Автор: dershokus 13.11.2012, 09:05

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

Код


1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, 28, 31, 31, 39, 40, 43, 45, 46, 55, 57, 58, 63, 63, 64, 67, 79, 81, 82

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

Код


1, 3, 4, 7, 13, 15, 31, 40, 63, 121, 127, 255, 364,

Автор: Akina 13.11.2012, 10:56

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

Автор: Silent 14.11.2012, 10:43

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

Код


#include <stdio.h>
#include <queue>
using namespace std;

struct compare  
{  
  bool operator()(const int& l, const int& r)  
  {  
      return l > r;  
  }  
};    

priority_queue <int, vector<int>, compare> M;

int main()
{
    M.push(1);
    for (int i = 1; i <= 1000; i++)
    {
        int x = M.top();
        M.pop();
        M.push(2*x+1);
        M.push(3*x+1);
        printf("%d ", x);
    }
    return 0;
}

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

Код


#include <stdio.h>

int main()
{
    int count = 0;
    for (int i = 1; count <= 1000; i++)
        if ((i == 1) || ((i-1) % 2 == 0) || ((i-1) % 3 == 0))
        {
            printf("%d ",i);
            count++;
        }
    return 0;
}

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

Автор: Фантом 14.11.2012, 11:31

Цитата(Silent @ 14.11.2012, 11:43

)

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

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

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

Код


#include <stdio.h>
int main()
{
    for (int i = 0; i < 1000; i+=6)
         printf("%d %d %d %d ",i+1,i+3,i+4,i+5);
    return 0;
}

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

Автор: Silent 14.11.2012, 12:34

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

Автор: Фантом 14.11.2012, 21:40

Цитата(Silent @ 14.11.2012, 13:34

)

Тем не менее, у меня еще есть второй вариант, который №1

Это да, но всерьез пользоваться возможностями C++, если явно не оговорено, что это можно, как-то нехорошо. smile

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

Автор: volatile 15.11.2012, 04:37

Код


#include <set>

void series (int cnt)
{
    std::set <int> a;
    a.insert (0);

    while (cnt --> 0)
    {
        int x = * a.begin () + 1;
        a.erase (a.begin ());
        a.insert (2 * x);
        a.insert (3 * x);
        std::cout << x << ' ';
    }
}

http://codepad.org/FKQFn95I

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

Цитата(dershokus @ 12.11.2012, 17:29

)

1000 неповторяющихся чисел

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

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

Цитата(Фантом @ 14.11.2012, 21:40

)

пользоваться возможностями C++ ... как-то нехорошо

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

Автор: Silent 15.11.2012, 08:12

Цитата(Фантом @ 14.11.2012, 21:40

)

Это да, но всерьез пользоваться возможностями C++, если явно не оговорено, что это можно, как-то нехорошо.

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

Код


#include <stdio.h>

const int N = 1000;
int M[N];
int head = 0,
    tail = 0;

void push(int x)
{
    int i;
    for (i = tail - (tail == N-1); (i > 0) && (M[i] > x); i--)
        M[i+1] = M[i];
    if (i < N) M[i+1] = x;
    tail++;
}

bool find(int x, int l, int r)
{
    int mid;
    if (M[r] < x ) return false;
    while (l < r)
    {
        mid = l + (r-l) / 2;
        if (x <= M[mid]) r = mid;
        else l = mid + 1;
    }
    if (M[r] == x) return true;
    else return false;
}

int main()
{
    M[0] = 1;
    while (tail < N)
    {
        int x = 2 * M[head] +1;
        if (!find(x,0,tail)) 
            push(x);
        int y = 3 * M[head] + 1;
        if (!find(y,0,tail)) push(y);
        head++;
    }
    for (int i = 0; i < N; i++) printf("%d ",M[i]);
    return 0;
}

Автор: volatile 15.11.2012, 23:41

Вот самый первый, который мне вчера пришел в голову (и самый тупой) вариант на простом массиве.
Если в языке больше ничо нет, то прокатит!

Код


int main ()
{
   const int size = 10000; // тут надо с запасом =))
   bool a [size] = {1};
   int n = 1000;
   int x = 0;

   while (n && x < size)
      if (a [x ++])
      {
         int y (x);
         do 
            if ((y += x) < size) 
               a [y] = 1;
         while (y < 3*x);
         std::cout << x << ' ';
         -- n;
      }
}

http://codepad.org/PVnrqXve

Автор: volatile 16.11.2012, 00:00

Цитата(Silent @ 15.11.2012, 08:12

)

предполагаю, что можно использовать хотя бы массивы

Не факт. Может в паскале нет массивов... (точно не могу сказать). В любом случае, массивы использовать нехорошо.
Вот (не менее тупой) вариант без массивов:

Код


bool 
is (int x)
{  if (-- x < 1) return !x;
   return 
         x%2==0 && is (x/2) 
      || x%3==0 && is (x/3);
}

int main ()
{
   int n = 1000; // Скока нуно циферок
   int x = 0;    // С какова начать (начнет со следущего, т.е с x+1)

   while (n) if (is (++ x))
   {
      std::cout << x << ' ';
      -- n;
   }
}

http://codepad.org/HTEJ7x8F

Не знаю, правда, насколько хорошо было использовать цЫклы ?
возможно в паскале цЫклов нет... (точно не могу сказать).

Добавлено через 8 минут и 2 секунды
Ну и модификация последнего алгоритма, с разбиением на столбики.
А то, у меня строка не влазила целиком в экран (моник слабоват).
Вот здесь циферки в 10 столбиков.

http://codepad.org/bnctfc43

Добавлено через 11 минут и 46 секунд
Последний вариант, должен быть медленней прочих.
Но зато он без специальных возможностей C++, как то:
Он без STL алгоритмов! Без контейнеров! И даже без простых массивов!
Ну и там можно начать печатать в любом порядке, и с любого элемента, не только 1-го.