|
Вопрос # 1 974/ вопрос открыт / |
|
Здравствуйте! Дали вот мне задачу...вроде не сложная...а вот че то не получается...в общем нужно сделать так чтобы при нажатии на кнопку в memo появились все простые числа в диапазоне от 1 до 100...нужно сделать либо через for либо через while либо через repeat
 |
Вопрос задал: Anrie (статус: Посетитель)
Вопрос отправлен: 7 октября 2008, 18:58
Состояние вопроса: открыт, ответов: 4.
|
Ответ #1. Отвечает эксперт: ANBsoft
Здравствуйте, Anrie!
Может не очень оптимально, но просто
Var f,n:Integer;
b:Boolean;
begin
for f:=1 to 100 do begin
b:=True;//Признак того что число простое
for n:=2 to f-1 do
if f mod n =0 then b:=False;
if b then Memo1.Lines.Add(IntToStr(f));
end;
end;
 |
Ответ отправил: ANBsoft (статус: Студент)
Время отправки: 7 октября 2008, 19:25
Оценка за ответ: 5
Комментарий к оценке: спасибо
|
Ответ #2. Отвечает эксперт: seryoga
Здравствуйте, Anrie!
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
mass = array [1..25] of integer;
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
procedure search;
end;
var
Form1: TForm1;
a:mass;
sizeA:integer;
implementation
{$R *.dfm}
{ TForm1 }
procedure TForm1.search;
var i,j:integer; fl:Boolean;
begin
a[1]:=2;
a[2]:=3;
sizea:=2;
for i:=5 to 100 do begin
fl:=false;
for j:=1 to sizea do
if i mod a[j] = 0 then fl:=true;
if not(fl) then
begin
inc(sizea);
a[sizea]:=i;
end;
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
var i:integer;
begin
search;
for i:=1 to sizeA do
Memo1.Lines.Add(inttostr(a[i]));
end;
end.
 |
Ответ отправил: seryoga (статус: 1-ый класс)
Время отправки: 7 октября 2008, 19:34
|
Ответ #3. Отвечает эксперт: Помфюк Владимир Степанович
Здравствуйте, Anrie!
Так же просто. но немного оптимальнее:
memo1.lines.clear;
memo1.lines.add('1');//деление на 1 проверять не будем
memo1.lines.add('2');//добавляем чтобы в первый раз сработал цикл от 1 до memo.lines.count-1 (2-1=1 for j:=1 to 1)
for i:=3 to 100 do begin
b:=True;
for j:=1 to memo1.lines.count-1 do
if (i mod StrToInt(memo1.lines[j]) = 0) Then b:=False;
if b then memo1.lines.add(IntToStr(i));
end;
можно ещё оптимальнее: 2 мы уже добавили, и соответственно уже знаем что все чётные числа нам не нужны:
memo1.lines.clear;
memo1.lines.add('1');
memo1.lines.add('2');
for i:=2 to 50 do begin //цикл в два раза быстрее
b:=True;
for j:=1 to memo1.lines.count-1 do
if ((i*2-1) mod StrToInt(memo1.lines[j]) = 0) Then b:=False;
if b then memo1.lines.add(IntToStr(i*2-1)); //2*2-1 = 3 , 50*2-1=99
end;
Ответ #4. Отвечает эксперт: Паровоз
Здравствуйте, Anrie!
Вот еще решето Эратосфена:
http://alglib.sources.ru/numbers/erat.php
 |
Ответ отправил: Паровоз (статус: 10-ый класс)
Время отправки: 7 октября 2008, 21:43
|
Мини-форум вопроса
Всего сообщений: 20; последнее сообщение — 10 октября 2008, 15:25; участников в обсуждении: 8.
|
Dron (статус: Студент), 7 октября 2008, 19:26 [#1]:
Цитата:
нужно сделать либо через for либо через while либо через repeat
Так и напрашивается вопрос: а есть другие варианты?
С уважением.
|
|
|
seryoga (статус: 1-ый класс), 7 октября 2008, 19:34 [#2]:
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
mass = array [1..25] of integer;
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
procedure search;
end;
var
Form1: TForm1;
a:mass;
sizeA:integer;
implementation
{$R *.dfm}
{ TForm1 }
procedure TForm1.search;
var i,j:integer; fl:Boolean;
begin
a[1]:=2;
a[2]:=3;
sizea:=2;
for i:=5 to 100 do begin
fl:=false;
for j:=1 to sizea do
if i mod a[j] = 0 then fl:=true;
if not(fl) then
begin
inc(sizea);
a[sizea]:=i;
end;
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
var i:integer;
begin
search;
for i:=1 to sizeA do
Memo1.Lines.Add(inttostr(a[i]));
end;
end.
|
|
|
seryoga (статус: 1-ый класс), 7 октября 2008, 19:56 [#3]:
to: Помфюк Владимир Степанович и ты считаешь что твой метод оптимальней?
|
|
|
ANBsoft (статус: Студент), 7 октября 2008, 20:03 [#4]:
Если хотите ускорить выполнение, то:
1) не нужно перебирать четные числа больше 2
2) как только признак простого стал False - выход из перебора
3) не нужно перебирать делители больше (n div 2+1)
|
|
|
ANBsoft (статус: Студент), 7 октября 2008, 20:04 [#5]:
то Dron: можно еще через goto 
|
|
Мережников Андрей (статус: Абитуриент), 7 октября 2008, 20:08 [#6]:
to Помфюк Владимир Степанович
Ваш последний вариант можно сделать еще оптимальнее, заменив цикл for J:=1... на следующую конструкцию:
b:=false;
j:=1;
repeat
b:=((i*2-1) mod StrToInt(memo1.lines[j]) = 0);
inc(j);
until (b)or(j=memo1.lines.count);
Зачем проверять делением на весь список, если уже встретится число, на которое делится без остатка.
to Бубырь Александр Николаевич
то, что Ваше решение "не очень оптимально" - это мягко сказано. можно элементарно оптимизировать заменив for n:=2 to f-1
на for n:=2 to (f div 2) Хотя про цикл for в данном случае я написал выше
|
|
|
Dron (статус: Студент), 7 октября 2008, 20:11 [#7]:
Цитата:
можно еще через goto
Да, о таком извращении я не подумал...
С уважением.
|
|
|
ANBsoft (статус: Студент), 7 октября 2008, 20:12 [#8]:
Скорее всего это задача по информатике в каком-то институте, моего решения вполне достаточно (чем проще тем лучше - меньше объяснять преподавателю что для чего), если нет - я привел варианты ускорения.
|
|
|
Мережников Андрей (статус: Абитуриент), 7 октября 2008, 20:24 [#9]:
to Seryoga
Вариант, предложенный Помфюком действительно оптимальней в плане выполнения - проверка выполняется только делением на уже найденные простые числа - это самый оптимальный вариант. (с учетом прекращения проверки при обнаружении делителя)
|
|
|
seryoga (статус: 1-ый класс), 7 октября 2008, 20:29 [#10]:
to Мережников Андрей а у меня как не так что ли?
|
|
|
Мережников Андрей (статус: Абитуриент), 7 октября 2008, 20:29 [#11]:
Конечно, если не считать варианта заполнения memo вручную из таблицы простых чисел:
with memo1.lines do
add('1');
add('2');
add('3');
add('5');
.....
add('...');
end;
to Dron - вот вам еще вариант кроме циклов и go to
|
|
|
Мережников Андрей (статус: Абитуриент), 7 октября 2008, 20:34 [#12]:
to Seryoga - извини, я не уточнил, что сравнивал с вариантом, предложенным Бубырь Александром
А в предложенном Вами варианте есть небольшой недостаток - для того, чтобы задать размер массива, либо надо знать точное количество простых чисел, либо использовать динамический массив. Согласитесь, что при изменении диапазона, например до 1000 знать количество простых чисел проблематично.
|
|
Вадим К (статус: Академик), 7 октября 2008, 23:57 [#13]:
Можно ещё оптимальней написать перебор. Проверять не до (m div 2), а до целой части корня квадратного с проверяемого числа. Конечно, сюда стоит включить только нечетные числа.
Конечно, если считать простые числа до сотни. то это не сильно будет заметно. А вот до миллиона - это уже заметно, так как в моём случае время будет расти обратно пропорционально квадрату, а в случае m/2 - линейно.
Галочка "подтверждения прочтения" - вселенское зло.
|
|
Помфюк Владимир Степанович (статус: Абитуриент), 8 октября 2008, 10:25 [#14]:
to Seryoga:
когда я начинал писать свой ответ, то был только Ответ №1. Мой вариант был немного быстрее
|
|
|
seryoga (статус: 1-ый класс), 8 октября 2008, 11:06 [#15]:
to Мережников Андрей:
Количество простых чисел r не превышает:
* trunc(1.6n/ln(n)+1), если n ≤ 200
* trunc(n/(ln(n)-2)+1), если n > 200
|
|
|
ANBsoft (статус: Студент), 8 октября 2008, 11:24 [#16]:
Да хватит меряться у кого длиннее быстрее. Судя по формулировке задачи (как я уже писал), это нужно для получения зачета по информатике, и изголяться, экономя каждый такт процессора, нет смысла (судя по тому, что автор не появляется - он получил что хотел). Практический смысл от такого алгоритма очень мал, требуемые в криптографии простые числа получают совсем другими путями.
|
|
|
Anrie (статус: Посетитель), 10 октября 2008, 14:55 [#17]:
Спасибо большое что помогли...я просто еще всего лишь в 11 классе и еще только начинаю изучать делфи...вот мне задали на уроке задачу повышенного уровня...ну это по сравнению с остальными одноклассниками....у меня были варианты...но я не смог додуматься до переменной типа boolean...
|
|
|
Вадим К (статус: Академик), 10 октября 2008, 15:06 [#18]:
по поводу boolean. А многие здесь на сайте вкурсе, что выражение вида
var c:boolean;
begin
c := 3 = 3;
вполне законно?
Галочка "подтверждения прочтения" - вселенское зло.
|
|
|
Помфюк Владимир Степанович (статус: Абитуриент), 10 октября 2008, 15:13 [#19]:
некоторые знают. но некторые предпочитают писать
c:=(3=3);
чтобы понятнее было
|
|
Пупкин В.В. (статус: 1-ый класс), 10 октября 2008, 15:25 [#20]:
я догадовался об этом! :=)
|
Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.
|
