Большие числа

Вопросы программирования на Free Pascal, использования компилятора и утилит.

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

Большие числа

Сообщение Evgen » 03.01.2019 05:20:33

Среди чисел от 1 до 10^10000 найти такие, что в своей записи имеют цифру 4.
Проблема не в поиске цифры 4, а проблема в диапазоне. Как работать в таком большом диапазоне?
Кто знает, помогите. Спасибо!
Evgen
новенький
 
Сообщения: 19
Зарегистрирован: 03.01.2019 05:10:14

Re: Большие исла

Сообщение Снег Север » 03.01.2019 16:15:41

С числами очень большой разрядности может работать библиотечка MPArith
http://www.wolfgang-ehrhardt.de/misc_en.html#mparith

Но думаю, дело намного проще - надо в строке, изображающей число, найти символ '4' :D
Аватара пользователя
Снег Север
долгожитель
 
Сообщения: 2990
Зарегистрирован: 27.11.2007 16:14:47

Re: Большие исла

Сообщение Vadim » 03.01.2019 16:48:26

Снег Север писал(а):Но думаю, дело намного проще - надо в строке, изображающей число, найти символ '4'

По мотивам великого и могучего математика Снег Север, равного по интеллекту Пьеру Ферма...
:-D
Код: Выделить всё
{$H+}
Uses SysUtils;
Var
  i, j: integer;
  s, n: string;
  F1, F2: TextFile;
  CurrNum: integer;
  Yes: boolean;

begin
  AssignFile(F1, 'numbers.txt');
  AssignFile(F2, 'the4yes.txt');
  Rewrite(F1);
  Rewrite(F2);
 
  Randomize;
 
  For i:=1 To 10000 Do
  Begin
    s:='';
    Yes:=False;
    For j:=1 To i Do
    Begin
      CurrNum:=Random(10);
      If CurrNum=4 Then
        Yes:=True;
      Str(CurrNum, n);
      s:=s+n;
    End;
    WriteLn(F1, s);
    If Yes Then
      WriteLn(F2, s);
  End;
  CloseFile(F1);
  CloseFile(F2);
end.

Evgen
Но будьте мужественны, дружище и не падайте в обморок - там чуть ли не в каждом числе будет присутствовать цифра "4", поэтому над алгоритмом генерации чисел подумайте сами... ;-)
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Re: Большие исла

Сообщение Дож » 03.01.2019 20:51:13

Evgen, что нужно выдать в качестве результата? Таких чисел 10^10000-9^10000, навряд ли человечество создало достаточно жёстких дисков, чтобы уместить весь их список.
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 899
Зарегистрирован: 12.10.2008 16:14:47

Re: Большие исла

Сообщение Vadim » 03.01.2019 21:13:04

Дож писал(а):Таких чисел 10^10000-9^10000, навряд ли человечество создало достаточно жёстких дисков, чтобы уместить весь их список.

Вряд ли требуется именно весь список таких чисел. :-) Пока что задача описана в чисто теоретическом смысле и практически выглядит как полная бессмыслица. Дело в том, что в таких больших числах, если условиться, что нужны именно длинные числа, цифра "4" бкдет присутствовать в каждом числе, так что тут даже искать ничего не надо... :-)
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Re: Большие исла

Сообщение Дож » 03.01.2019 21:17:18

Пока что задача описана в чисто теоретическом смысле и практически выглядит как полная бессмыслица

Поэтому нужно уточнить задачу у тс.
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 899
Зарегистрирован: 12.10.2008 16:14:47

Re: Большие исла

Сообщение Vadim » 03.01.2019 21:37:01

Дож писал(а):Поэтому нужно уточнить задачу у тс.

Никак нельзя. Ему препод в институте такое задал. И если он сразу не спросил, а придёт с уточняющим вопросом только после праздников - у препода возникнет подозрение, что дело тут нечисто... :-D
Я думаю, ему надо самому попробовать подумать над внесением в задачу элементов реальности, т.е. ограничений. В принципе наводку (и даже с примером) ему уже дали, осталось только детали додумать.
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Re: Большие числа

Сообщение Evgen » 08.01.2019 01:42:38

Всем спасибо, но пока ответа не увидел на свой вопрос. Уточняю условие задачи. Имеется N коробок с номерами от 1 до N. Подсчитать количество коробок в номере которых встречается цифра 4 (N от 1 до 10^10000 и задача должна выполнятся 2 сек., память - 256 МіБ). Я пробовал работать со строками, но задача проходит только до N=100000000, а дальше зависает. Вот мой код программы:
program korob;
var n,i,j,k:longint; s,s1:ansistring;
begin
readln(n);
k:=0; s:='';
for i:=1 to n do begin str(i,s1);
for j:=1 to length(s1) do
if (s1[j]='4') then
begin k=k+1; break end
end;
writeln(k);
end.
Тут понятно,что тип longint не подходит для такого большого N, вот я и не знаю как поступить, может какие то динамические массивы, но как с ними работать я не знаю. И уважаемый Снег Север как работать с библиотечкой MPArith не понял. Помогитееееее
Evgen
новенький
 
Сообщения: 19
Зарегистрирован: 03.01.2019 05:10:14

Re: Большие числа

Сообщение Vadim » 08.01.2019 04:18:23

Evgen писал(а):Тут понятно,что тип longint не подходит для такого большого N,

Мало того, тут понятно, что вообще ни один числовой тип не подходит. ;-) -D
Для Вашего случая:
1. Число должно быть представлено в виде строки. Сразу. Без любых промежуточных преобразований.
2. Поиск в строке цифры "4" делать стандартной функцией "Pos()".
Evgen писал(а):и задача должна выполнятся 2 сек., память - 256 МіБ)

:-D
А вот это уже будет зависеть от количества обрабатываемых строк с числами и от того, чем ещё, окромя Вашей программы, будет загружен компутер... ;-)
Evgen писал(а):может какие то динамические массивы, но как с ними работать я не знаю.

Вы там у себя динамические массивы по учебной программе ещё не проходили? Если нет, то и не надо их использовать. Зачем бежать впереди паровоза? ;-)
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Re: Большие числа

Сообщение Лекс Айрин » 08.01.2019 05:00:45

Vadim, скорее всего, задача немного сложнее. Сама постановка намекает на использование какого-то трюка. Ведь просто нереально на таком оборудовании перелопатить столько чисел за такое время. Имхо, надо искать какую-то зависимость.
Аватара пользователя
Лекс Айрин
долгожитель
 
Сообщения: 5723
Зарегистрирован: 19.02.2013 16:54:51
Откуда: Волгоград

Re: Большие числа

Сообщение Vadim » 08.01.2019 08:13:56

Лекс Айрин писал(а):скорее всего, задача немного сложнее. Сама постановка намекает на использование какого-то трюка. Ведь просто нереально на таком оборудовании перелопатить столько чисел за такое время. Имхо, надо искать какую-то зависимость.

Трюк не трюк, однако и в такой постановке есть вещи несомненные:
- Сами числа, для начала, нужно как-то получить. Надеюсь против этого ты возражать не будешь? :-) Так вот, вне зависимости от кол-ва ОЗУ, генерация чисел будет очень-очень-очень долгая...
Всё, на этом можно останавливаться, т.к. условие в 2 секунды уже не выполняется. ;-)
А вот, к примеру, если использовать многопоточность, то тут есть возможность ускориться, т.к. каждое число не зависит друг от друга, следовательно его обработку можно и нужно растарабанить на потоки.
И тут мы сталкиваемся со второй трудностью: скажи мне, что ты думаешь о реализации многопоточности в FreePascal? :-D
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Re: Большие числа

Сообщение VirtUX » 08.01.2019 08:32:28

Сделаю намек вопросом: "Почему все решили, что НОМЕР коробки в диапазоне от 1 до 1^10000 ? Где это есть в условии?"
Аватара пользователя
VirtUX
энтузиаст
 
Сообщения: 880
Зарегистрирован: 05.02.2008 10:52:19
Откуда: Крым, Алушта

Re: Большие числа

Сообщение Vadim » 08.01.2019 08:37:23

Кстати, на счёт трюка. ;-)
Если использовать массив для поразрядного хранения числа, то длина массива получается 10001 ячейка, что вполне влазиет в стандартный паскалевский тип.
Количество ячеек должно быть 10^10000 штук. А вот это уже не влезает. Но ведь не обязательно хранить все числа в одном массиве? Но тут мы опять входим в противоречие с постановкой задачи. По ней, все числа уже есть, следовательно генерировать их нет необходимости. Беда в том, что в память 256 МБ они не влезают, следовательно хранятся на диске. И вот тут то мы и попались: чтение с диска - операция долгая... Читать и, следовательно, обрабатывать надо порциями. Опять не влезаем в 2 секунды.

Добавлено спустя 2 минуты 36 секунд:
VirtUX писал(а):Где это есть в условии?"

Evgen писал(а): Имеется N коробок с номерами от 1 до N
...
N от 1 до 10^10000

Т.е. кол-во коробок может быть и 10^10000 штук. А значит и номер тоже...
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Re: Большие числа

Сообщение sign » 08.01.2019 08:42:03

Evgen писал(а):Всем спасибо, но пока ответа не увидел на свой вопрос. Уточняю условие задачи. Имеется N коробок с номерами от 1 до N. Подсчитать количество коробок в номере которых встречается цифра 4 (N от 1 до 10^10000 и задача должна выполнятся 2 сек., память - 256 МіБ).

Уточняйте задание.
Возможно опечатка, я поверю в такое - (1 <= N <= 10000), нежели в (1 <= N <= 10^10000).

Возможно препод специально поставил такое условие, чтобы проверить, понимает студент вообще, что можно, а что нельзя?
sign
энтузиаст
 
Сообщения: 1131
Зарегистрирован: 30.08.2009 09:20:53

Re: Большие числа

Сообщение Vadim » 08.01.2019 08:43:55

На всякий случай... ;-)
У нас в универе как-то раз была задачка о вычислении высоты орбиты спутника. Так вот, по заданным исходным данным, спутник должен был летать на высоте -90 км от уровня моря...
:-D

Добавлено спустя 3 минуты 18 секунд:
sign писал(а):Возможно препод специально поставил такое условие, чтобы проверить, понимает студент вообще, что можно, а что нельзя?

Я уже об этом говорил выше. К сожалению теперь реакция препода на любой ответ будет только отрицательной, т.к. слишком много времени прошло с момента выдачи задания. В отличие от моего варианта со спутником, где сначала требовался расчёт, тут вобщем то с первого взгляда видно, что кое-что не влезает в стандартные паскалевские типы данных.
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

След.

Вернуться в Free Pascal Compiler

Кто сейчас на конференции

Сейчас этот форум просматривают: Yandex [Bot] и гости: 1

Рейтинг@Mail.ru