Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Решето Эратосфена, рекурсивным путём 
V
    Опции темы
ressac
Дата 2.11.2009, 11:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 345
Регистрация: 25.11.2006

Репутация: нет
Всего: 1
http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%...%B5%D0%BD%D0%B0

я вот сделал, только не очень мне нравится :(

может кто-то сможет более проще и элегантней написать это?

Код

void eratostenes(int,int[],int);
void mult(int,int,int[],int);

int main()
{
    int x;
    int N=20;
    int v[N];

    for (x=0; x<N; x++)
        v[x]=1;

    eratostenes(2,v,N);

    for (x=0; x<N; x++)
        printf("\n%3i <-> %i",x+1,v[x]);
}

void eratostenes(int pos, int v[], int N)
{
    if (pos*pos < N)
    {
        if (v[pos-1])
            mult(pos,pos,v,N);

        eratostenes(pos+1,v,N);
    }
}

void mult(int m, int pos, int v[], int N)
{
    if (pos < N)
    {
        if (v[pos])
        {
            int x = (pos+1)%m;
            if(!x)
                v[pos]= x;
        }

        mult(m,pos+1,v,N);
    }
}


Это сообщение отредактировал(а) ressac - 2.11.2009, 11:59
PM MAIL   Вверх
17dufa
Дата 2.11.2009, 12:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 324
Регистрация: 2.3.2006

Репутация: 3
Всего: 5
ressac, Ваша функция mult слегка непонятна. 
почему Вы не остановились на тупом переводе приведенного в вики псевдокода на си?
PM MAIL   Вверх
ressac
Дата 2.11.2009, 13:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 345
Регистрация: 25.11.2006

Репутация: нет
Всего: 1
я просто сделал поиск методом деления.
вы думаете лучше сделать так как в вики? smile
попробую ща...
PM MAIL   Вверх
azesmcar
Дата 2.11.2009, 13:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211
Код

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

int main()
{
    const int n = 500;
    std::vector<int> arr(n, 0);

    int i = 1;
    for (std::vector<int>::iterator it = arr.begin(); it != arr.end(); ++it)
        *it = ++i;

    for (int p = 2; p <= n; ++p)
        for (int i = 2; i * p - 2 < n; ++i)
            arr[i * p - 2] = 0;

    std::remove_copy_if(
        arr.begin(),
        arr.end(),
        std::ostream_iterator<int>(std::cout, " "),
        std::bind1st(std::equal_to<unsigned int>(), 0));
}

так подойдет? хотя это не самое оптимальное решение.

Это сообщение отредактировал(а) azesmcar - 2.11.2009, 13:51
PM   Вверх
ressac
Дата 2.11.2009, 13:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 345
Регистрация: 25.11.2006

Репутация: нет
Всего: 1
там мне в рекурсивном виде надо ;)
PM MAIL   Вверх
ressac
Дата 2.11.2009, 14:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 345
Регистрация: 25.11.2006

Репутация: нет
Всего: 1
вот я переделал mult

Код

void mult(int m, int pos, int v[], int N)
{
    if (pos*m <= N)
    {
        if(v[pos*m-1])
            v[ pos * m-1 ] = 0;

        mult(m+1,pos,v,N);
    }
}
PM MAIL   Вверх
17dufa
Дата 2.11.2009, 15:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 324
Регистрация: 2.3.2006

Репутация: 3
Всего: 5
ressac, усе, до меня дошло. На Вашем месте, я бы переделал mult вот в такое:
Код

void mult(int pos, int step, int v[], int N)
{
    if (pos <= N)
    {
        v[pos] = 0;
        mult(pos+step,v,N);
    }
}

и вызывал бы соответственно так:
Код

void eratostenes(int pos, int v[], int N)
{
    if (pos*pos < N)
    {
        if (v[pos-1])
            mult(pos*pos,pos,v,N);
        eratostenes(pos+1,v,N);
    }
}
PM MAIL   Вверх
ressac
Дата 2.11.2009, 16:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 345
Регистрация: 25.11.2006

Репутация: нет
Всего: 1
ты опробывал у себя это? у меня виснит
PM MAIL   Вверх
17dufa
Дата 3.11.2009, 11:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 324
Регистрация: 2.3.2006

Репутация: 3
Всего: 5
ressac, нет конечноsmile начнем с того, что мой код просто в том виде, что здесь лежит не билдится))) я пытался задать направление. вот работающий код:
Код

void mult(int pos, int step, int v[], int N)
{
    if (pos <= N)
    {
        v[pos-1] = 0;
        mult(pos+step, step,v,N);
    }
}

void eratostenes(int pos, int v[], int N)
{
    if (pos*pos < N)
    {
        if (v[pos-1])
            mult(pos*pos,pos,v,N);
        eratostenes(pos+1,v,N);
    }
}

то есть в функции mult надо v[pos-1] = 0; а не v[pos] = 0.
С именами бы тоже чего-нить сделать не мешало.

а откуда такая любовь к рекурсии? на функциональный язык планируете перейти?

Это сообщение отредактировал(а) 17dufa - 3.11.2009, 11:18
PM MAIL   Вверх
ressac
Дата 3.11.2009, 20:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 345
Регистрация: 25.11.2006

Репутация: нет
Всего: 1
да нет просто это задачи из универа

а вообще рекурсия нравится сама по себе smile
PM MAIL   Вверх
17dufa
Дата 5.11.2009, 10:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 324
Регистрация: 2.3.2006

Репутация: 3
Всего: 5
ressac, главное не увлекайтесь. в C++ хвостовую рекурсию в цикл компилятор преобразовывать, насколько я знаю, не будет. в данной задаче, например, решение с циклами должно быть эффективнее и думаю многим, в частности мне, будет понятнее. 
и имена все-таки поменяйте smile 
PM MAIL   Вверх
Lazin
Дата 5.11.2009, 11:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154
Код

#light
open System 
open Microsoft.FSharp.Collections

let primesUnderOneMillion = seq { 
    yield 2 
    let knownComposites = HashSet.Create()

    for i in 3 .. 2 .. int 1E6 do 
            
        let found = knownComposites.Contains(i) 
        if not found then 
            yield i 

        do for j in i .. i .. int 1E6 do 
               knownComposites.Add(j) |> ignore 
    } 

for x in primesUnderOneMillion do
    printfn "%d" x


Это сообщение отредактировал(а) Lazin - 5.11.2009, 11:09


--------------------
C++ is the steampunk of programming languages: modern ideas realized with victorian technology.
PM MAIL Skype GTalk   Вверх
17dufa
Дата 5.11.2009, 12:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 324
Регистрация: 2.3.2006

Репутация: 3
Всего: 5
Lazin, класс. а что за язык? и один косяк - автора интересует рекурсия. циклы ему не по душе smile 
*а что делает |> ignore ? и внутренний цикл можно начинать не с i, а с i*i
PM MAIL   Вверх
Lazin
Дата 5.11.2009, 13:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154
Цитата(17dufa @  5.11.2009,  12:27 Найти цитируемый пост)
что за язык?

F#
Цитата(17dufa @  5.11.2009,  12:27 Найти цитируемый пост)
и один косяк - автора интересует рекурсия. циклы ему не по душе

согласен, но это и не цикл в традиционном понимании, это ленивая последовательность smile 
Цитата(17dufa @  5.11.2009,  12:27 Найти цитируемый пост)
а что делает |> ignore

оператор |> берет то, что справа и передает в ф-ю слева, в данном случае эта ф-я применяется для того, что-бы компилятор не ругался на игнорируемое возвращаемое значение
Цитата(17dufa @  5.11.2009,  12:27 Найти цитируемый пост)
и внутренний цикл можно начинать не с i, а с i*i

нет, нельзя
допустим i = 3, тогда в хэш таблицу попадут числа начиная с 9, а нужно, что-бы попали - 3, 6, 9, 12 итд
угу, можно

Это сообщение отредактировал(а) Lazin - 5.11.2009, 13:12


--------------------
C++ is the steampunk of programming languages: modern ideas realized with victorian technology.
PM MAIL Skype GTalk   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0725 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.