Модераторы: korob2001, ginnie
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Усовершенствовать алгоритм поиска. 
:(
    Опции темы
lanD
Дата 5.6.2006, 21:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Программа неэффективна. Например, она анализирует четные числа больше 2, хотя очевидно, что они не могут быть простыми. Усовершенствуйте алгоритм поиска простых чисел.
Код

#!/usr/bin/perl -w
$maxprimes=20; # Необходимо найти только первые 20 простых чисел
$value=1;
$count=0;
while($count < $maxprimes) {
    $value++;
    $composite=0;
OUTER: for($i=2; $i<$value;$i++) {
       for($j=$i; $j<$value; $j++) {
            if(($j*$i)==$value) {
                $composite=1;
            }
       }
}
if (! $composite) {
    $count++;
    print "Число $value простое\n";
}
}
 
PM MAIL   Вверх
igorold
Дата 6.6.2006, 08:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 557
Регистрация: 22.12.2005
Где: Россия->Урал-& gt;Миасс

Репутация: 3
Всего: 17
Держи, студент  smile 
Код

#!/usr/bin/perl
use strict;
use DBI;

my $DebugFile;
open($DebugFile, ">>","simpl") or die("Error opening debug file\n");
use integer;

my $maxprimes=20; # Необходимо найти только первые 20 простых чисел
my $value=2;
my $count=0;
my $composite=0;
my ($i, $j);
my @simpl = (2);
my $max;
my $rez;

while($count < $maxprimes)
{
    $value++;
    $composite=1;
    $max = $value / $simpl[0];
    for ($i=0; $i<$count;$i++)
    {
        if ($simpl[$i]>$max) {last;}
        $rez = ($value/$simpl[$i])*$simpl[$i];
        if ($rez==$value)
        {
            $composite=0;
            last;
        }
        $max = $value / $simpl[$i];
    }
    if ($composite)
    {
        $count++;
        $simpl[$count] = $value;
    }
}

print $DebugFile "Простые числа: @simpl\n";

no integer;
exit(0);
1;


какие средства убыстрения поиска:
1. Формируется массив простых чисел
2. число проверяется на делитель только простого числа
3. если следующее простое число больше, чем значение/предыдущее простое число, то цикл прерывается
поясню: возьмем число 29, если оно не делиться на 2, 3, 5, то дальше деление проверяться не будет ...  
4. происходит выход из цикла проверок при нахождении первого делителя
5. можешь сделать еще одно убыстрение - после $value == 3 делать приращение +2, т.е. не проверять заведомо четные числа - попробуй сам сделать ...     

Это сообщение отредактировал(а) igorold - 6.6.2006, 09:03


--------------------
... у семи нянек 14 сисек ...  
Putin here, Putin there, Putin almost everywhere!
PM MAIL   Вверх
lanD
Дата 6.6.2006, 09:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Студентка  smile
Спасибо!

Добавлено @ 09:47 
Кстати, я это задание выполняла по книге "Освой сво Perl за 24 часа"!
И я ещё не дошла до массивов :-) вот только начинаю... так что задание можно было выполнить с стандартными while, for, if.... ну и т.д. 
PM MAIL   Вверх
igorold
Дата 6.6.2006, 09:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 557
Регистрация: 22.12.2005
Где: Россия->Урал-& gt;Миасс

Репутация: 3
Всего: 17
т.е. тебе надо сделать без массива?
тогда тебе надо использовать способы ускорения 3-5 

сделаешь без массива или тебе помочь?  smile  smile  

Кстати, увеличение на 2 я сделал так:

Код

............
while($count < $maxprimes)
{
    if ($value>=3) { $value++;}    # <---- вот эта строчка добавлена
    $value++;
    $composite=1;
.................
 

Это сообщение отредактировал(а) igorold - 6.6.2006, 10:05


--------------------
... у семи нянек 14 сисек ...  
Putin here, Putin there, Putin almost everywhere!
PM MAIL   Вверх
lanD
Дата 6.6.2006, 10:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Нет спасибо ты и так помог, я уже сама дальше.
Если во время изучения у меня будут появляться кое-какие вопросы, я буду спрашивать если можно smile 
PM MAIL   Вверх
vumnik
Дата 6.6.2006, 10:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
А вот мой вариант. Тоже на делителях и без массивов.

Код

$min = 2;
$flag = 1;

while ($flag) {
    $max += 100;
    #цикл по проверяемым числам
   NEW: foreach $i ($min..$max) {
        #цикл по числам, которыми проверяем
        foreach $j (2..$i-1) {
            #есил деление по модулю даёт нам ноль хотябы в одном случае
            #то считаем число не простым и переходим на следующую итерацию
            unless ($i%$j) { next NEW; }
        }
        #если не было переходов по метке, то считаем число простым
        $count++;
        print "$count: $i\n";
        #есил нашли нужное количество простых чисел завершаем программу
        if ($count == 20) {
            $flag = 0;
            last;
        }
        last if $flag == 0;
    }
    $min = $max;
}
 
PM MAIL   Вверх
igorold
Дата 6.6.2006, 14:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 557
Регистрация: 22.12.2005
Где: Россия->Урал-& gt;Миасс

Репутация: 3
Всего: 17
Хороший вариант, а теперь осталось только его оптимизировать ...  smile  


--------------------
... у семи нянек 14 сисек ...  
Putin here, Putin there, Putin almost everywhere!
PM MAIL   Вверх
lanD
Дата 7.6.2006, 01:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Нужно модифицировать программу чтобы фигурка печаталась в вертикальном положении...
Код

#!/usr/bin/perl -w

@words=qw( Интернет Ответ Принтер Программа );
$guesses[0]="";
$wrong=0;

$choice=$words[rand @words];
$hangman="0-|--<";
@letters=split(//, $choice);
@hangman=split(//, $hangman);
@blankword=(0) x scalar(@hangman);
OUTER:
    while ($wrong<@hangman) {
        foreach $i (0..$#letters) {
            if ($blankword[$i]) {
                print $blankword[$i];
            } else {
                print "-";
            }
        }
        print "\n";
        if ($wrong) {
            print @hangman[0..$wrong-1]
        }
        print "\n Ваш выбор: ";
        $guess=<STDIN>; chomp $guess;
        foreach(@guesses) {
            next OUTER if ($_ eq $guess);
        }
        $guesses[$#guesses]=$guess;
        $right=0;
        for ($i=0; $i<@letters; $i++) {
            if ($letters[$i] eq $guess) {
                $blankword[$i]=$guess;
                $right=1;
            }
        }
        $wrong++ unless($right);
        if (join('', @blankword) eq $choice) {
            print "Вы угадали! Загаданное слово было $choice\n";
            exit;
        }
    }
    print "$hangman\n Печально, но было загадано слово $choice!\n";
    

 
PM MAIL   Вверх
igorold
Дата 7.6.2006, 08:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 557
Регистрация: 22.12.2005
Где: Россия->Урал-& gt;Миасс

Репутация: 3
Всего: 17
lanD, чтобы фигурка печаталась в вертикальном положении, т.е. каждый символ на новой строке, если я правильно понял, нужно после каждого символа фигуры вставлять (печатать) \n
т.е. строку 
Код

print @hangman[0..$wrong-1]

можно заменить на 
Код

for ($s=0;$s<$wrong;$s++) { print "$hangman[$s]\n" }

соответственно и в конце вместо
Код

print "$hangman\n Печально, но было загадано слово $choice!\n";

вставить
Код

for ($s=0;$s<$wrong;$s++) { print "$hangman[$s]\n" }
print " Печально, но было загадано слово $choice!\n";

ну и человечка переписать на 
Код

$hangman="0|-||A";

 
или так:
Код

...................
$hangman=" O !/A\\! V !J L!---";
.....................
@hangman=split(/!/, $hangman);
..................
 

Это сообщение отредактировал(а) igorold - 7.6.2006, 08:18


--------------------
... у семи нянек 14 сисек ...  
Putin here, Putin there, Putin almost everywhere!
PM MAIL   Вверх
sharq
Дата 7.6.2006, 09:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Perl Liker
**


Профиль
Группа: Участник
Сообщений: 841
Регистрация: 13.12.2004
Где: Ростов-на-Дону

Репутация: 23
Всего: 28
igorold, 
Цитата(igorold @  7.6.2006,  09:10 Найти цитируемый пост)
for ($s=0;$s<$wrong;$s++) { print "$hangman[$s]\n" }

Ты на Perl пишешь, к чему здесь Сишные циклы? Используй foreach и постфиксную запись!

Кстати, если помогаешь человеку, то пиши код с 
Код

use strict;

Чтобы он сразу привыкал к хорошему стилю программирования на Perl.

 smile  


--------------------
[color=gray]There's More Than One Way To Do It[/color]
PM MAIL WWW ICQ Skype   Вверх
lanD
Дата 7.6.2006, 10:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Вообщето я она.

Цитата(sharq @  7.6.2006,  09:52 Найти цитируемый пост)
Ты на Perl пишешь, к чему здесь Сишные циклы? Используй foreach и постфиксную запись!

Такое задание было...



Цитата(igorold @  7.6.2006,  08:10 Найти цитируемый пост)
нужно после каждого символа фигуры вставлять (печатать) \n

Так в принципе я  и делала.
Цитата(sharq @  7.6.2006,  09:52 Найти цитируемый пост)
use strict;

Я ещё незнаю даже что это такое не дошла. 
PM MAIL   Вверх
igorold
Дата 7.6.2006, 11:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 557
Регистрация: 22.12.2005
Где: Россия->Урал-& gt;Миасс

Репутация: 3
Всего: 17
sharq, а где вы увидели, что я не пишу 
Код

use strict;
смотрим 2-й пост -> Дата 6.6.2006, 08:36

а насчет Ты на Perl пишешь, к чему здесь Сишные циклы? Используй foreach и постфиксную запись!

так я не профи ... во-вторых человеку никто не отвечал ... а я ответил ... в третьих, а что этот цикл в перле не работает?
а что такое постфиксная запись? а в 4-х на этом форуме я сам учусь ...  


--------------------
... у семи нянек 14 сисек ...  
Putin here, Putin there, Putin almost everywhere!
PM MAIL   Вверх
sharq
Дата 8.6.2006, 17:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Perl Liker
**


Профиль
Группа: Участник
Сообщений: 841
Регистрация: 13.12.2004
Где: Ростов-на-Дону

Репутация: 23
Всего: 28
lanD, советую тебе писать все свои скрипты с
Код

use strict 

igorold в первом своем примере использовал эту прагму, посмотри в чем отличие + почитай perldoc strict и можешь воспользоваться поиском, здесь уже об этом говорилось.

igorold, 
Цитата(igorold @  7.6.2006,  12:08 Найти цитируемый пост)
в третьих, а что этот цикл в перле не работает?

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

Цитата(igorold @  7.6.2006,  12:08 Найти цитируемый пост)
а что такое постфиксная запись?

в данном случае:
Код

print "..." for ...;



Цитата(igorold @  7.6.2006,  12:08 Найти цитируемый пост)
так я не профи 

так и я тоже  smile 

 smile  


--------------------
[color=gray]There's More Than One Way To Do It[/color]
PM MAIL WWW ICQ Skype   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Perl"
korob2001
sharq
  • В этом разделе обсуждаются общие вопросы по языку Perl
  • Если ваш вопрос относится к системному программированию, задавайте его здесь
  • Если ваш вопрос относится к CGI программированию, задавайте его здесь
  • Интерпретатор Perl можно скачать здесь ActiveState, O'REILLY, The source for Perl
  • Справочное руководство "Установка perl-модулей", можно скачать здесь

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

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


 




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


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

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