[РЕШЕНО] Длинная арифметика [pascal]
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
[РЕШЕНО] Длинная арифметика [pascal] - 2010-11-25 22:05:05.583333
|
|
|
v0lume
Сообщений: 310
Оценки: 0
Присоединился: 2009-10-22 20:48:37.160000
|
знаю, решается в пару действий на jаvа, но нужен паскаль.
есть входной файл. в нём 2 строчки. каждая строчка содержит 1000чезначное число. нужно считать эти два числа и распихать по двум массивам.
string не пройдёт, не влазит (max 255). integer тоже самое.
почитал про eoln() и eof(). попробовал использовать eoln:
while not eoln(input) do
for i:=1000 downto 1 do
read(input,a[i]);
в input:
12345
54321 на выходе при выводе пустой файл.
подскажите в чём ошибка. может есть другой метод считывания - поделитесь.
|
|
|
|
|
RE: Длинная арифметика [pascal] - 2010-11-26 00:42:50.063333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
А куда ты, собственно, выводишь то? В приведённом коде - никуда :)
Если там дальше и правда есть вывод в консоль/файл, то проверь в дебаггере значение массива `a` после считывания и до вывода.
|
|
|
|
|
RE: Длинная арифметика [pascal] - 2010-11-26 02:16:57.576666
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Напиши свой тип данных. В чём проблема-то?
|
|
|
|
|
RE: Длинная арифметика [pascal] - 2010-11-26 14:22:51.696666
|
|
|
v0lume
Сообщений: 310
Оценки: 0
Присоединился: 2009-10-22 20:48:37.160000
|
saz
так в скалярных не может быть больше 256 элементов.
kreol
массив пустой. выводил последние элементы - пусто. дальше обработка значений и вывод в файл.
есть у кого ещё идеи?
|
|
|
|
|
RE: Длинная арифметика [pascal] - 2010-11-26 15:27:45.866666
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
Не парь себе мозг. Во-первых, храни младшие разряды с младшими индексами (hi-endian). То есть:for i:=1 upto 1 do
read(input,a[i]);Так на самом деле будет проще – меньше геморроя с индексами. И почти циклы все будут upto, а не downto.
Во-вторых, если string не умеет больше 255 символов, заведи просто массив char'ов. Если в паскале есть массивы переменного размера – то это самое то, что нужно. Если нет, ну выдели фиксированного размера массив, в тысячу элементов. Правда при этом как-то придётся хранить информацию о длине числа в массиве, но тут есть два варианта: либо тип record с массивом и полем used_elems_count, либо терминатор – первый элемент массива, в котором нету цифры будет содержать какое-нибудь специальное значение, скажем 'a'.
|
|
|
|
|
RE: Длинная арифметика [pascal] - 2010-11-26 16:09:24.460000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Тфу, блин, чё-та затупил. У тебя цикл совершенно не такой, как должен быть. Что нужно сделать:
1) считать всё: пока не конец файла, считывать строки;
2) пока пока не конец строки, считывать символы в массив.
а у тебя получается:
1) пока не конец (первой) строки, считывать по 1000 символов в массив.
Если индексы точные, то по идее одна строка должна считаться, но лучше сразу править.
Попробуй (a - двухмерный массив 2x1000, i - номер строки, j - номер столбца):
i = 0;
j = 0;
while not eof(input) do begin
while not eoln(input) do begin
read(input, a[i, j]);
inc(j);
end;
inc(i);
end;
|
|
|
|
|
RE: Длинная арифметика [pascal] - 2010-11-27 14:44:09.063333
|
|
|
Davey
Сообщений: 45
Оценки: 0
Присоединился: 2010-03-24 14:51:57.760000
|
Для того чтобы строки были длинными - директива компилятора {$H+}. Но это так - для расширения кругозора… ^^
Строки использовать, разумеется, не надо.
Полезные функции, типо работы с длинными числами, лучше один раз написать, и хранить где-нибудь в коллекции своих модулей, чтобы когда надо что-то очень быстро написать, всё было под рукой.
Вот тебе минимальный наборчик. Тут отдельно функции считывания, вывода, сложения, вычитания, умножения на обычное число и на длинное и сравнение длинный чисел.
Хранятся в массиве целых чисел, где разбиты по базе 10^3.
Писал больше 2-х лет назад, когда был не особо грамотным, но вроде бы работает ^___^
Type
TLong = array[-1..10003] of integer;
const
base = 1000;
baselen = 3;
function readLong : Tlong;
var
s : String;
i, j, k : integer;
x : TLong;
begin
readln(S);
while length(s) mod baselen <> 0 do
s := '0' + s;
Fillchar (x, sizeof(x), 0);
x[0] := length(s) div baselen;
k := 0;
for i := x[0] downto 1 do begin
For j := 1 to baselen do begin
inc(k);
x[i] := x[i] * 10 + strtoint(s[k]);
end;
end;
readLong := x;
end;
function EQ (var x, y :Tlong) : shortint;
var
i : integer;
begin
if x[0] > y[0] then begin
EQ := 1;
exit;
end;
if x[0] < y[0] then begin
EQ := -1;
exit;
end;
For i := x[0] downto 1 do begin
if x[i] > y[i] then begin
EQ := 1;
exit;
end;
if x[i] < y[i] then begin
EQ := -1;
exit;
end;
end;
EQ := 0;
end;
function sum (var a, b : TLong) :Tlong;
var
i, j, t : integer;
C : TLong;
begin
fillchar(c, sizeof(c), 0);
c[0] := max(a[0], b[0]);
t := 0;
for i := 1 to c[0] do begin
r := r + a[i] + b[i];
c[i] := t mod base;
t := t div base;
end;
if t <> 0 then begin
inc(c[0]);
c[c[0]] := t;
end;
sum := c;
end;
procedure writelong(var x : TLong);
var
i : integer;
S : String;
begin
write(x[x[0]]);
For i := x[0] - 1 downto 1 do begin
s := inttostr(x[i]);
while length(s) < baselen do
s:= '0' + s;
write(s);
end;
writeln;
end;
function sub (var a, b : TLong) : Tlong;
var
i, t : integer;
c : Tlong;
begin
fillchar(c, sizeof(c), 0);
t := 0;
For i := 1 to a[0] do begin
t := a[i] - b[i];
if t < 0 then begin
dec(a[i+1]);
t := t + base;
end;
c[i] := t;
end;
c[0] := a[0];
while (c[c[0]] = 0) and (c[0] > 1) do dec(c[0]);
sub := c;
end;
function scalmul(var a : Tlong; c : integer) : TLong;
var
i, t : integer;
B : TLong;
begin
fillchar(b, sizeof(b), 0);
b[0] := a[0];
t := 0;
for i := 1 to b[0] do begin
t := t + a[i] * c;
b[i] := t mod base;
t := t div base;
end;
while (t <> 0) do begin
inc(b[0]);
b[b[0]] := t mod base;
t := t div base;
end;
scalmul := b;
end;
function mul (var a, b : TLong) : TLong;
var
c : Tlong;
i, j, t : integer;
begin
fillchar(c, sizeof(c), 0);
for i := 1 to a[0] do begin
t := 0;
For j := 1 to b[0] do begin
t := t + c[i + j - 1] + a[i] * b[j];
c[i + j - 1] := t mod base;
t := t div base;
end;
j := b[0] + i;
while t <> 0 do begin
c[j] := t mod base;
t := t div base;
inc(j);
end;
end;
c[0] := MaxN;
while (c[c[0]] = 0) and (c[0] > 1) do
dec(c[0]);
mul := c;
end;
|
|
|
|
|
RE: Длинная арифметика [pascal] - 2010-11-27 17:55:22.993333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
2 Davey:
Директивы компилятору зависят от компилятора, а длинных строк в ранних версиях Паскаля не было. Позже (может уже даже в Delphi) появились и динамические строки, и статические неограниченной размерности.
|
|
|
|
|
RE: Длинная арифметика [pascal] - 2010-11-27 20:41:33.923333
|
|
|
Davey
Сообщений: 45
Оценки: 0
Присоединился: 2010-03-24 14:51:57.760000
|
quote:
ORIGINAL: kreol
Директивы компилятору зависят от компилятора, а длинных строк в ранних версиях Паскаля не было.
В борландском и в фрипаскале вроде бы работает. Хотя, соглашусь, в ранних версиях наверное не было.
Просто я сильно молодой и такие компиляторы старше меня ;)
|
|
|
|
|
RE: Длинная арифметика [pascal] - 2010-11-29 23:11:25.730000
|
|
|
v0lume
Сообщений: 310
Оценки: 0
Присоединился: 2009-10-22 20:48:37.160000
|
davey
мне что то твои функции совсем не понравились.
нашёл другое решение:
a:array[0..1000] of integer;
s:char;
i:integer;
--------------------------------
i:=1;
while (s>+'0') and (s<='9') do begin
a[i]:=s;
inc(i);
read(s);
end;
a[o]:=i-1;
--------------------------------
записываем всю строку в массив. i-1 будет длинной массива.
так же считывается вторая строка. если нужно сделать математические операции кроме сравнения - переворачиваем массив. если только сравнить, можно не переворачивать.
|
|
|
|
|
RE: Длинная арифметика [pascal] - 2010-11-30 14:36:12.140000
|
|
|
Davey
Сообщений: 45
Оценки: 0
Присоединился: 2010-03-24 14:51:57.760000
|
А чем же тебе мои функции не понравились? У меня то без всяких переворачиваний, строк, и к тому же по базе 3, что оптимизирует и память и быстродействие.
Я абиделся :'(
|
|
|
|
|
RE: Длинная арифметика [pascal] - 2010-11-30 21:19:48.100000
|
|
|
v0lume
Сообщений: 310
Оценки: 0
Присоединился: 2009-10-22 20:48:37.160000
|
тем и не понравился, что говно.
в частности строкой
readln(s); при s:string;
не знаю насчёт скорости, но по-моему ты не считаешь строку длиннее 256 символов. в моём же случае нужно считать строку длинной в 1000 символов.
не люблю я всякие примудрости в коде, когда можно написать его же пусть и примитивно, но зато он будет универсален (правую границу можно расширить вплоть до >30000 элементов).
моё мнение было сформированно путём только поверхностного анализа твоего когда. я его не разбирал т.к. он мне не нравится.
|
|
|
|
|
RE: Длинная арифметика [pascal] - 2010-11-30 21:52:51.430000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: v0lume
не люблю я всякие примудрости в коде, когда можно написать его же пусть и примитивно, но зато он будет универсален (правую границу можно расширить вплоть до >30000 элементов).
Вся "премудрость" того кода в том, что он работает в системе счисления 2^32 (или 2^64? longint – это сколько?). Твой работает в системе с основанием 10. Тому коду потребуется выполнить в 9-10 раз меньше операций при сложении, и в 81-100 раз меньше операций при умножении.
Правда у него есть свой недостаток: накладные расходы на переводы из одной системы счисления в другую. Что победит – скорость выполнения операций или скорость перевода из одной системы в другую, – будет зависеть от конкретной задачи. Если считать два числа, сложить и вывести результат – то проще это сделать в десятичной системе. Если же вместо сложения надо будет выполнить вычисления на десяток сложений/умножений, то быстрее считать в системе по основанию 2^32.
|
|
|
|
|
RE: Длинная арифметика [pascal] - 2010-12-01 03:24:28.240000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: v0lume
тем и не понравился, что говно.
Тебе указали на директиву компилятору. Тебе показали вариант без директив. Ты не разобрался ни в одном из них и после этого говоришь, что код - говно?
|
|
|
|
|
|
