Форум программистов, компьютерный форум, киберфорум
Наши страницы
PascalABC.NET
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Dprod
0 / 0 / 0
Регистрация: 25.11.2016
Сообщений: 17
1

Последовательность

19.10.2017, 20:57. Просмотров 895. Ответов 8
Метки нет (Все метки)

На контрольной работе по информатике Анатолию досталось задание, написать программу подсчета наибольшего числа идущих подряд простых чисел в числовой последовательности Х1, … , ХN, где 0 < Xk < 109, k=1,…,N и 1< N < 100000. Помогите Анатолию написать программу.
Формат входных данных. В первой строке входного файла input.txt записано целое число N – количество натуральных чисел исходной последовательности. А в следующей строке через пробел записано N элементов данной последовательности.
Формат выходных данных. Запишите в выходной файл output.txt наибольшее число идущих подряд простых чисел, а если в последовательности нет простых чисел, то вывести 0.

Я тут написал:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
var f: text;
a: integer;
am: array of integer;
fam: integer;
i: integer;
ni: integer;
s: integer;
sm: array of integer;
fsm: integer;
begin
assign(f, 'input.txt');
reset(f);
readln(f, a);
am:= new integer[a];
sm:= new integer[a]; 
 
 fam:=0;
 while not eof(f) do begin
  writeln(a);
  read(f, a);
  am[fam]:=a;     
  fam:=fam+1;
 end;
 
 while i<fam do begin
  for ni:=1 to am[i] do begin 
   if (am[i] mod ni = 0) then s:=s+1;  
  end;
  if (s=2) then sm[fsm]:= sm[fsm]+1 else fsm:=fsm+1;
  s:=0;
  i:=i+1;
 end;
close(f);
s:=0;
 
if (fsm>0) then begin
  for i:=0 to fsm-1 do begin
 
  if (i<fsm-1) then begin
   if (sm[i]<sm[i+1])  then s:=sm[i+1];
  end;
  end;
  end;
  writeln(s);
  
assign(f, 'output.txt');
rewrite(f);
write(f, s);
close(f);
end.
Но выдаёт ошибку, как решить верно?
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.10.2017, 20:57
Ответы с готовыми решениями:

Считать последовательность цифр и преобразовать ее в последовательность соответствующих латинских букв
Пожалуйста можете помочь, с решением вот такой задачи. Задание: Считать последовательность цифр и...

Задана последовательность символов, за которой следует точка(в саму последовательность точка не входит).Напеча
Задана последовательность символов, за которой следует точка(в саму последовательность точка не...

Дана последовательность А1...А50. Получить новую последовательность, исключив отрицательные элементы
Дана последовательность А1...А50. Получить новую последовательность, исключив отрицательные элементы

2. Дана целочисленная последовательность. Определить количество вхождений каждого числа в последовательность
Написал программу var a,c:array of integer; count,i,p,u: integer; begin for i:=1 to 10 do...

Вставить в последовательность число так, чтобы последовательность осталась неубывающей.
Дана последовательность действительных чисел а1&lt;=а2...&lt;=an. Вставить в нее действительное число b...

8
Joy
Эксперт Pascal/Delphi
2163 / 1194 / 1434
Регистрация: 29.08.2014
Сообщений: 4,376
20.10.2017, 06:36 2
если ничего не напутал, то так:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function IsPrime(n,m:integer):boolean:=(m=1?true:(n mod m<>0) and (IsPrime(n,m-1)));
var
  n,x,c,d:integer;
begin
  readln(n);
  for n:=1 to n do begin
    read(x);
    if (x<>1) and (IsPrime(x,trunc(sqrt(x)))) then c:=c+1 
    else
      begin
        if c>d then d:=c;
        c:=0;
      end;
  end;
  if c>d then d:=c;
  writeln(d);
end.
0
JuriiMW
1956 / 1053 / 1562
Регистрация: 10.12.2014
Сообщений: 3,891
20.10.2017, 06:47 3
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function isPrime(n : Integer) : Boolean;
begin
  Result := False;
  if (n >= 5) and (Pred(n) mod 6 = 0) or (Succ(n) mod 6 = 0) then
    begin
      for var d := 2 to trunc(sqrt(n)) do
        if n mod d = 0 then Exit;
      Result := True;
    end
  else
    Result := (n = 2) or (n = 3);
end;
 
function p(var c : Integer; d : Integer := 1) : Integer;
begin
  if d = 1 then c += 1 else c := 0;
  Result := c;
end;
 
begin
  var a := ReadArrInteger(ReadLnInteger);
  var c := 0;
  Write(a.Select(n->isPrime(n)?p(c):p(c,0)).max);
end.
Добавлено через 2 минуты
Joy, ваша функция считает 1 простым числом!
0
Joy
Эксперт Pascal/Delphi
2163 / 1194 / 1434
Регистрация: 29.08.2014
Сообщений: 4,376
20.10.2017, 06:53 4
JuriiMW, знаю, поэтому в коде написал это
Цитата Сообщение от Joy Посмотреть сообщение
if (x<>1) and
Добавлено через 5 минут
у меня другой косяк - для чисел 109 - переполнение программного стека
0
JuriiMW
1956 / 1053 / 1562
Регистрация: 10.12.2014
Сообщений: 3,891
20.10.2017, 07:14 5
Лучший ответ Сообщение было отмечено Dprod как решение

Решение

Для небольшого количества функция проверки простоты числа — это нормально.
Но, при больших — лучше заранее рассчитать все простые числа до максимального из входных данных:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function isPrime(n : Integer) : Boolean;
begin
  Result := False;
  if (n >= 5) and (Pred(n) mod 6 = 0) or (Succ(n) mod 6 = 0) then
    begin
      for var d := 2 to trunc(sqrt(n)) do
        if n mod d = 0 then Exit;
      Result := True;
    end
  else
    Result := (n = 2) or (n = 3);
end;
 
function p(var c : Integer; d : Integer := 1) : Integer;
begin
  if d = 1 then c += 1 else c := 0;
  Result := c;
end;
 
begin
  var a := ReadArrInteger(ReadLnInteger);
  var prim := range(2,a.Max).Where(n->isPrime(n)).ToArray;
  var c := 0;
  Write(a.Select(n->prim.indexOf(n)>-1?p(c):p(c,0)).max);
end.
Так программа займёт больше памяти, но сократится время её выполнения.
0
Joy
Эксперт Pascal/Delphi
2163 / 1194 / 1434
Регистрация: 29.08.2014
Сообщений: 4,376
20.10.2017, 07:48 6
ох и долго же он до миллиарда массив заполняет, даже если делить на уже найденные простые числа...
0
JuriiMW
1956 / 1053 / 1562
Регистрация: 10.12.2014
Сообщений: 3,891
20.10.2017, 08:49 7
Да уж… Чёт я погорячился ;–)
С массивом простых чисел был неправ.
Для данных, заполненных
Код
  var a := ArrRandomInteger(100000, 100, 1000000000);
первая программа быстро выдаёт ответ… А вторая… За 5 минут не дождался ответа.
0
Joy
Эксперт Pascal/Delphi
2163 / 1194 / 1434
Регистрация: 29.08.2014
Сообщений: 4,376
20.10.2017, 09:17 8
для оптимального, нужно заранее рассчитать в файл простые числа до 109, а уже потом проверять все остальное.
0
volvo
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
26149 / 17526 / 6950
Регистрация: 22.10.2011
Сообщений: 30,864
Записей в блоге: 6
20.10.2017, 13:15 9
JuriiMW, 5 минут - слишком много. Тут надо другие способы определения массива простых чисел. Например, старое доброе решето Эратосфена, которое на моей заполняется до миллиарда чуть больше чем за 18 секунд (да еще и через VirtualBox), но никак не минутами.

Либо мемоизация (как только нашел функцией isPrime простое число - занес его в массив простых чисел, и перед началом проверки - посмотреть, может очередной кандидат уже был проверен ранее), это ускорит программу относительно того, что есть сейчас, ибо если в исходных данных будут подряд записаны 999999733, 999996983, 999997967, 999999607, 999999613, 999999667, 999999677, 999999733, 999999733, 999996983, 999999733, 999996983, 999999733, 999996983 - то твоя программа резко замедлится, а при использовании мемоизации замедление будет гораздо меньше: 999999733 будет проверяться не 5 раз, а всего один (только не надо говорить, что пары десятков таких больших простых чисел подряд в файле не может быть. Для целей тестирования я бы и пару 999999733, 999996983 записал 50 тысяч раз, и посмотрел бы, сколько участников сразу отсеялось бы, не желая ждать неделями, пока отработает их брутфорсный код)
1
20.10.2017, 13:15
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.10.2017, 13:15

дана последовательность вещественных чисел а1,а2,.а15 Определить являеться ли последовательность упорядоченной по возрастанию
дана последовательность вещественных чисел а1,а2,...а15 Определить являеться ли последовательность...

Вводится последовательность натуральных чисел. Признак конца ввода – 0. определить является ли последовательность геометрической прогрессией
Помогите пожалуйста написать программу на языке Паскаль, без использования массива.

Вводится последовательность из N целых чисел, отличных от нуля. Определить, сколько раз последовательность меняет знак
Вводится последовательность из N целых чисел, отличных от нуля. Определить, сколько раз...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru