Дана пооследовательность из 100 чисел, как определить связаны ли элементы этой последовательности геометрической програссией, а главное как вывести самую длинную прогрессию ?

Здравствуйте, Аноним, Вы писали:

А>Дана пооследовательность из 100 чисел, как определить связаны ли элементы этой последовательности геометрической програссией, а главное как вывести самую длинную прогрессию ?

у геометрической прогрессии есть коэффициент:
a[i+1] = coeff*a[i], я прав?
если все 100 чисел целые, то просто перебираешь все coeff от 1 до упора(до тех пор пока a[0]*coeff <= a[99]) и для каждого coeff
проверяешь сколько чисел подряд связаны в прогрессию с коэффицентом coeff.
все результаты сохраняешь, потом выбираешь coeff с максимальным количеством элементов

приблизительно — так, это если я с тем, что такое прогрессия не наврал

а вообще, по этой теме, наверное в "алгоритмы"

Здравствуйте, Аноним, Вы писали:

А>Дана пооследовательность из 100 чисел, как определить связаны ли элементы этой последовательности геометрической програссией, а главное как вывести самую длинную прогрессию ?
А в чем проблема? Ты не знаешь что такое геометрическая прогрессия?

Здравствуйте, Аноним, Вы писали:

А>Дана пооследовательность из 100 чисел, как определить связаны ли элементы этой последовательности геометрической програссией, а главное как вывести самую длинную прогрессию ?

1) Если предполагается, что последовательность может быть перемешана — отсортировать.
2) Проверить, выполняется ли соотношение x[k]:x[k+1] == x[k+1]:x[k+2] для всех смежных пар.
3) Если предполагается, что в последовательности кроме прогрессии встречается мусор — применить статистические методы.
Например, прологарифмировать; логарифм геометрической прогрессии — это арифметическая прогрессия. Проверить, насколько последовательность похожа на прямую — большого труда не составит.

Здравствуйте, Аноним, Вы писали:

А>Дана пооследовательность из 100 чисел, как определить связаны ли элементы этой последовательности геометрической програссией,

Сначала, если последовательность не упорядочена, отсортировать ее, например, по-возрастанию.
Затем, выяснить, множитель георметрической прогрессии (или как он там правильно называется) делением второго элемента на первый.
И наконец, проверить для каждого оставшегося члена получается ли он произвдением предыдущего члена на множитель.


A>а главное как вывести самую длинную прогрессию ?

А что это такое ?

Здравствуйте, Кодт, Вы писали:

К>Проверить, насколько последовательность похожа на прямую — большого труда не составит.

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

Вообще, решение — руль!

Здравствуйте, misha_sk, Вы писали:

_>Здравствуйте, Аноним, Вы писали:

А>>Дана пооследовательность из 100 чисел, как определить связаны ли элементы этой последовательности геометрической програссией,

Допустим есть 10 чисел
1, 3, 6, 12, ...

_>Сначала, если последовательность не упорядочена, отсортировать ее, например, по-возрастанию.

отсортировали
1, 3, 6, 12, ...


_>Затем, выяснить, множитель георметрической прогрессии (или как он там правильно называется) делением второго элемента на первый.

k = 3 / 1 = 3

_>И наконец, проверить для каждого оставшегося члена получается ли он произвдением предыдущего члена на множитель.

k = 3
6 != 3 * k, => последовательность содержит два элемента

A>>а главное как вывести самую длинную прогрессию ?

_>А что это такое ?

то, что первая последовательность содержит всего два числа 1 и 3 где k = 3
потом идет вторая последовательность 3, 6, 12 где k = 2
поэтому самая длинная будет последовательность 3, 6, 12

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Аноним, Вы писали:

А>>Дана пооследовательность из 100 чисел, как определить связаны ли элементы этой последовательности геометрической програссией, а главное как вывести самую длинную прогрессию ?

К>1) Если предполагается, что последовательность может быть перемешана — отсортировать.

уже ошибка. вот проверь:

1, -2, 4, -8, 16, -32, 64, 3, 5

после сортировки имеем:

-32, -8, -2, 1, 3, 4, 5, 16, 64

получается, самая толстая прогрессия

-32, -8, -2

у которой знаменатель прогрессии = -0.5

а реально имеем геометрическую прогрессию

1, -2, 4, -8, 16, -32, 64

у которой знаменатель прогрессии = -2

Здравствуйте, ssm, Вы писали:

ssm>уже ошибка. вот проверь:



Можно сделать иначе:
1. сортируем по абсолютной величине, и, если знаменатель не +/- 1, отсееваем совпадающие элементы;
2. лабаем функцию по алгоритму:
а) пусть дана последовательность b_1, ..., b_n, и знаменатель q, тогда, если выполняется условие b_n = q^(n-1)*b_1, выполняем операцию (а) для подпоследовательности b_2, ..., b_n-1, увеличивая длину прогресси на 2, если условеие не выполняется, то выполняем (а) последовательно для b_1, ..., b_n-1, а за тем для b_2, ..., b_n, выбирая максимум из длин соответствующих подпоследовательностей.
3. найдя таким образом знаменатель(и максимальную длину прогресси), можно попробовать вывести эту самую прогрессию. 8)

Здравствуйте, Аноним, Вы писали:

А>у геометрической прогрессии есть коэффициент:
А>a[i+1] = coeff*a[i], я прав?
А>если все 100 чисел целые, то просто перебираешь все coeff от 1 до упора(до тех пор пока a[0]*coeff <= a[99]) и для каждого coeff
А>проверяешь сколько чисел подряд связаны в прогрессию с коэффицентом coeff.
А>все результаты сохраняешь, потом выбираешь coeff с максимальным количеством элементов

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

Здравствуйте, gribunin, Вы писали:


G>Проще отсортировать прогрессию по возрастанию, а потом делить числа на предыдущие, начиная с большего. Как только результат деления отличается от предыдущего результата деления, значит текущая прогрессия закончилась, началась следующая.

коэффициент то может быть < 0

Здравствуйте, unforgiven_hero, Вы писали:

_>Здравствуйте, ssm, Вы писали:

ssm>>уже ошибка. вот проверь:
_>)


_>Можно сделать иначе:
_>1. сортируем по абсолютной величине, и, если знаменатель не +/- 1, отсееваем совпадающие элементы;
_>2. лабаем функцию по алгоритму:
_>а) пусть дана последовательность b_1, ..., b_n, и знаменатель q, тогда, если выполняется условие b_n = q^(n-1)*b_1,

опять знак теряется при отрицательном коэфициенте и нечетном n!!!

2, -4, 8, -16, 4

какую 4-ку будешь отсеивать ?

проше всего последовательность не сортировать а предположить, что последовательность уже правильно отсортированна

Здравствуйте, ssm, Вы писали:

ssm>Здравствуйте, gribunin, Вы писали:


ssm>коэффициент то может быть < 0

Да, согласен, не подумал.

А какая максимальная последовательность здесь?

    1 2 3 4 8 9 16 27 32

По-моему такая

    1 2 4 8 16 32

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

Здравствуйте, ssm, Вы писали:

ssm>опять знак теряется при отрицательном коэфициенте и нечетном n!!!
ну, дык, надо же пралльно корни извлекать, т.е. я имею в виду, то, что при нечетном n, и четном (n-1) надо проверять два случая с q = +/- sqr(b_n/b_1, n-1). Я думаю, что это уже не принципиально! 8)

ssm>2, -4, 8, -16, 4
ssm>какую 4-ку будешь отсеивать ?
ту(те), которая(ые) не удовлетворяет(ют) знакочередованию последовательности!

так, например, {2, -4, 8, -16, 32} ((n = 5)%2 != 0 && (q = -2) < 0)
будет выполнятся следующим образом:
так как уже не надо ничего сортировать, просто запускаем алгоритм.
вычисляем начальное значение q: q^(n-1)*b_1 = b_n => q^4*2 = 32 => q = +/- 2; от и усе, вроде... хех, аль нет?

ssm>проше всего последовательность не сортировать а предположить, что последовательность уже правильно отсортированна

В условии об этом речь не идет 8)

Здравствуйте, Аноним, Вы писали всякое, но я попрошу:

Пожалуйста, конкретизируй формулировку своей проблемы, подробнее распиши, а то тут народ из-за "расплывчатого" условия...
Я прочитал несколько раз — не совсем понял некоторорые детали.

Здравствуйте, unforgiven_hero, Вы писали:

_>так, например, {2, -4, 8, -16, 32} ((n = 5)%2 != 0 && (q = -2) < 0)
_>будет выполнятся следующим образом:
_>так как уже не надо ничего сортировать, просто запускаем алгоритм.
_>вычисляем начальное значение q: q^(n-1)*b_1 = b_n => q^4*2 = 32 => q = +/- 2; от и усе, вроде... хех, аль нет?

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

1, 2, 4, 8, 16, 32, 64, 256, 1024, 4096, 16834, 65536, ...
получается две последовательности:

b0 = 1, q = 2, n = 7
b0 = 1, q = 4, n = 9

сечешь?

Здравствуйте, ssm, Вы писали:

накалякал я перед сном, чтобы спать спокойней
вот в общем тестовый массив:

1, 2, 4, 8, 16, 32, 64, 256, 1024, 4096, 16384, 65536, -2, -8

сам алгоритм можно в 10 строчках уместить.
выводит все геометрические прогресии, отсортированные по количеству элементов ней.
первая естественно — самая жирная:

output:

1, 2, -2, 4, 8, -8, 16, 32, 64, 256, 1024, 4096, 16384, 65536,
b0 = 1, q = 4, n = 9 : {1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, }
b0 = 4, q = 4, n = 8 : {4, 16, 64, 256, 1024, 4096, 16384, 65536, }
b0 = 1, q = 2, n = 7 : {1, 2, 4, 8, 16, 32, 64, }
b0 = 16, q = 4, n = 7 : {16, 64, 256, 1024, 4096, 16384, 65536, }
b0 = 2, q = 2, n = 6 : {2, 4, 8, 16, 32, 64, }
b0 = 64, q = 4, n = 6 : {64, 256, 1024, 4096, 16384, 65536, }
b0 = 1, q = -2, n = 5 : {1, -2, 4, -8, 16, }
b0 = 1, q = 16, n = 5 : {1, 16, 256, 4096, 65536, }
b0 = 4, q = 2, n = 5 : {4, 8, 16, 32, 64, }
b0 = 256, q = 4, n = 5 : {256, 1024, 4096, 16384, 65536, }
b0 = -2, q = -2, n = 4 : {-2, 4, -8, 16, }
b0 = 4, q = 16, n = 4 : {4, 64, 1024, 16384, }
b0 = 8, q = 2, n = 4 : {8, 16, 32, 64, }
b0 = 16, q = 16, n = 4 : {16, 256, 4096, 65536, }
b0 = 1024, q = 4, n = 4 : {1024, 4096, 16384, 65536, }
b0 = 1, q = 8, n = 3 : {1, 8, 64, }
b0 = 1, q = -8, n = 3 : {1, -8, 64, }
b0 = 1, q = 32, n = 3 : {1, 32, 1024, }
b0 = 1, q = 64, n = 3 : {1, 64, 4096, }
b0 = 1, q = 256, n = 3 : {1, 256, 65536, }
b0 = 2, q = 4, n = 3 : {2, 8, 32, }
b0 = 2, q = -4, n = 3 : {2, -8, 32, }
b0 = 4, q = -2, n = 3 : {4, -8, 16, }
b0 = 4, q = 8, n = 3 : {4, 32, 256, }
b0 = 4, q = 64, n = 3 : {4, 256, 16384, }
b0 = 16, q = 2, n = 3 : {16, 32, 64, }
b0 = 16, q = 64, n = 3 : {16, 1024, 65536, }
b0 = 64, q = 16, n = 3 : {64, 1024, 16384, }
b0 = 256, q = 16, n = 3 : {256, 4096, 65536, }
b0 = 4096, q = 4, n = 3 : {4096, 16384, 65536, }
Press any key to continue

вот исходник:

#include <algorithm>
#include <vector>
#include <iostream>

const int ciArr[] = 
{
    1, 2, 4, 8, 16, 32, 64, 256, 1024, 4096, 16834, 65536, -2, -8
};

struct MyLess
{
    bool operator()(int lh, int rh) const
    {
        return abs(lh) < abs(rh);
    }
};

const int len = sizeof(ciArr) / sizeof(ciArr[0]);
std::vector<int> vec(ciArr, ciArr + len);

struct Holder
{
    int b0;
    int q;
    int n;

    Holder(int b0, int q, int n)
        : b0(b0), q(q), n(n)
    {
    }

    struct Greater
    {
        bool operator()(const Holder &lh, const Holder &rh) const
        {
            return lh.n > rh.n;
        }
    };

    struct Print
    {
        inline void operator()(const Holder &obj) const;
    };
};

int main()
{
    std::vector<Holder> holders;
    
    std::sort(vec.begin(), vec.end(), MyLess());
    std::cerr << "sorted vector\n\n";
    for(int i = 0; i < len; ++i)
    {
        std::cerr << vec[i] << ", ";
    }
    std::cerr << "\n";


    //find b0
    for(int i = 0; i < len - 1; ++i)
    {
        int b0 = vec[i];

        //find b1 and q
        for(int j = i + 1; j < len; ++j)
        {            
            int bn = vec[j];
            int q = bn / b0;
            int n = 2;
            
            //find bn
            for(int k = j + 1; k < len; ++k)
            {
                if(bn * q == vec[k])
                {
                    bn = vec[k];
                    ++n;
                }
            }
            if(n > 2)
            {
                holders.push_back(Holder(b0, q, n));
            }
        }
    }

    std::sort(holders.begin(), holders.end(), 
        Holder::Greater());

    std::for_each(holders.begin(), holders.end(), 
        Holder::Print());

    return 0;
}


inline void Holder::Print::operator()(const Holder &obj) const
{
    std::cerr << "b0 = " << obj.b0 << ", ";
    std::cerr << "q = " << obj.q << ", ";
    std::cerr << "n = " << obj.n;

    int bn = obj.b0;
    std::cerr << " : {" << bn << ", ";                        
    for(int i = 1; i < obj.n; ++i)
    {
        bn = bn * obj.q;
        std::cerr << bn << ", ";
    }

    std::cerr << "}\n";
}

Здравствуйте, ssm, Вы писали:

ssm>1, 2, 4, 8, 16, 32, 64, 256, 1024, 4096, 16834, 65536, ...
ssm>получается две последовательности:

ssm>b0 = 1, q = 2, n = 7
ssm>b0 = 1, q = 4, n = 9

ssm>сечешь?

))
все, кроме двух вещей:
1. на что тама нужно — "..."? 8)
2. никак не пойму, к чему ты это мне говоришь? ....у меня все и так работает

P.S. релизация твоего алгоритма(тот, что ниже/выше... не важно), на первый взгляд, довольно громосткая и вообще, перебор — это "руль" 8)

Здравствуйте, Аноним, Вы писали:

А>Дана пооследовательность из 100 чисел, как определить связаны ли элементы этой последовательности геометрической програссией, а главное как вывести самую длинную прогрессию ?

to ssm: 4, 10, 25, ... — Сечешь?

to Author:
Пару уточнений:
1. В задаче не сказано, может ли быть так, что числа последовательности будут дробными; 8)
2. Но тем более, необходимо ли учитывать факт целочисленности знаменателя!


вообщем, вот...

typedef    unsigned int    uint;
const    uint    N    = 11;

void    main()
{
    float    Seq[N]    = {1, 2, 4, 8, 16, 32, 64, 256, 1024, 4096, 16384};
    //float    Seq[N]    = {1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1};    // тута глючит, ну и х.. :D
    float    MaxB, MaxQ, MaxN    = 0, k;        // пояснять названия переменных не имеет значения 8)

    for(uint b = 0; b < N; b++)
        for(uint q = 0; q < N; q++)
            if(q != b && (Seq[q]/Seq[b] > 1.0f || Seq[q]/Seq[b] < -1.0f))
            {
                k = Seq[b];
                for(uint n = 2; true; n++)
                {
                    k *= Seq[q]/Seq[b];
                    for(uint i = 0; i < N; i++)
                        if(q != i && Seq[i]/k == Seq[q]/Seq[b])
                            break;
                    if(i == N)
                        break;
                }
                if(n >= MaxN)
                {
                    MaxN    = n;
                    MaxQ    = Seq[q]/(MaxB = Seq[b]);
                }
            }
}