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

[Evgen]

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

[Снег Север]

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

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

[Vadim]

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

По мотивам великого и могучего математика Снег Север, равного по интеллекту Пьеру Ферма...

Код: Выделить всё

{$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", поэтому над алгоритмом генерации чисел подумайте сами...

[Дож]

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

[Vadim]

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

Вряд ли требуется именно весь список таких чисел. Пока что задача описана в чисто теоретическом смысле и практически выглядит как полная бессмыслица. Дело в том, что в таких больших числах, если условиться, что нужны именно длинные числа, цифра "4" бкдет присутствовать в каждом числе, так что тут даже искать ничего не надо...

[Дож]

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

Поэтому нужно уточнить задачу у тс.

[Vadim]

Поэтому нужно уточнить задачу у тс.

Никак нельзя. Ему препод в институте такое задал. И если он сразу не спросил, а придёт с уточняющим вопросом только после праздников - у препода возникнет подозрение, что дело тут нечисто...
Я думаю, ему надо самому попробовать подумать над внесением в задачу элементов реальности, т.е. ограничений. В принципе наводку (и даже с примером) ему уже дали, осталось только детали додумать.

[Evgen]

Всем спасибо, но пока ответа не увидел на свой вопрос. Уточняю условие задачи. Имеется 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 не понял. Помогитееееее

[Vadim]

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

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

и задача должна выполнятся 2 сек., память - 256 МіБ)

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

может какие то динамические массивы, но как с ними работать я не знаю.

Вы там у себя динамические массивы по учебной программе ещё не проходили? Если нет, то и не надо их использовать. Зачем бежать впереди паровоза?

[Лекс Айрин]

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

[Vadim]

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

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

[VirtUX]

Сделаю намек вопросом: "Почему все решили, что НОМЕР коробки в диапазоне от 1 до 1^10000 ? Где это есть в условии?"

[Vadim]

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

Добавлено спустя 2 минуты 36 секунд:

Где это есть в условии?"

Имеется N коробок с номерами от 1 до N
...
N от 1 до 10^10000

Т.е. кол-во коробок может быть и 10^10000 штук. А значит и номер тоже...

[sign]

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

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

Возможно препод специально поставил такое условие, чтобы проверить, понимает студент вообще, что можно, а что нельзя?

[Vadim]

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


Добавлено спустя 3 минуты 18 секунд:

Возможно препод специально поставил такое условие, чтобы проверить, понимает студент вообще, что можно, а что нельзя?

Я уже об этом говорил выше. К сожалению теперь реакция препода на любой ответ будет только отрицательной, т.к. слишком много времени прошло с момента выдачи задания. В отличие от моего варианта со спутником, где сначала требовался расчёт, тут вобщем то с первого взгляда видно, что кое-что не влезает в стандартные паскалевские типы данных.