Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Object Pascal: кроссплатформенные технологии > увеличение памяти...


Автор: Рыська 11.7.2005, 00:55
Здравствуйте, я практически полный чайник в программировании smile и мне задали программу, в которой не хватает памяти для реализации... не могли бы вы рассказать пару приемчиков или показать пару простейших примеров как это можно сделать...

Автор: Romtek 11.7.2005, 01:26
Использовать оверлеи и дополнительную память EMS, XMS.
А лучше всего - оптимизировать потребление памяти.

GetMem/FreeMem.

Автор: vadims 11.7.2005, 09:00
Рыська Уточни что делает программа и на что именно расходуется и для чего не хватает памяти - вариантов решений может быть много

Автор: Remiznik 11.7.2005, 11:56
точно ... а ешё лудше выложи исходник программы ))))

Автор: Рыська 11.7.2005, 15:09
вообщем просто надо вывести на экран число 2^500... вот и все,
выглядит это число так: 3273390607896141870013189696827599152216642046043064789483291368096133796404674554883270092325904157150886684127560071009217256545885393053328527589376
но паскаль мне выводит его только до 17 знака... smile и как дальше жить?

Автор: vadims 11.7.2005, 15:38
Вообщем у тебя здесь проблемы спамятью вообще нет
Просто чисел такой разрядности не поддерживает ни один из стандартных типов переменных

Кокретно решение приводить сейчас нет времени но подход примерно следующий
Тебе нужно найти алгоритмы умножений через сложения (как строятся микропрограммы для реализации умножений)
и поэтапно их реализовывая ты будеш получать следующие цифры своего числа и выводить их

Вообщем либо в поисковик либо в 'Алгоритмы'

Автор: Рыська 11.7.2005, 15:43
vadims, спасибо большое=)

Автор: TP@MB@Y 11.7.2005, 17:35
Рыська

Я на первом курсе сдавал подобную задачку, только там надо было посчитать факториал большого числа.
Вот исходник (думаю ты сможешь разобраться и заменить факториал на 2^n):
Код

program faktorial;
uses crt;
const predel=152;
var i,j,k,n:integer;
    f:array[1..predel] of integer;
    ch:char;
{?®¤бзҐв Є®«-ў  жЁда зЁб« }
function kol_cif(a:integer):integer;
var s,q:integer;
begin
 q:=1;
 s:=10;
 while a div s<>0 do
  begin s:=s*10;q:=q+1;end;
 kol_cif:=q;
end;
{?ҐаҐе® ­  б«Ґ¤гойЁ© а §ап¤}
procedure razryad;
var x:integer;
begin
for x:=0 to i do
if kol_cif(f[i-x])>1 then begin
                          f[i-x-1]:=f[i-x-1]+(f[i-x] div 10);
                          f[i-x]:=f[i-x] mod 10;
                          end;
end;
{’…‹Ћ ??Ћѓ?ЂЊЊ›}
begin
repeat
 {‚ў®¤ ¤ ­­ле}
 repeat
  clrscr;
  writeln('‚ўҐ¤ЁвҐ зЁб«®, д Єв®аЁ « Є®в®а®Ј® е®вЁвҐ Ї®бзЁв вм');
  readln(n);
  if n<0 then begin
              textcolor(4);
              writeln('›››››››!!! >I ');
              delay(50000);
              textcolor(7);
              end;

 until n>=0;
f[predel]:=1;
for i:=1 to predel-1 do
f[i]:=0;
{‡ Ї®«­Ґ­ЁҐ "а §ап¤­®Ј®" ¬ ббЁў }
for j:=1 to n do
   for i:=1 to predel do
       begin
        f[i]:=f[i]*j;
        razryad;
       end;
{?а®ЇгбЄ "Їгбвле" а §а冷ў}
for i:=1 to predel do
if f[i]<>0 then begin k:=i;break end;
{‚лў®¤ аҐ§г«мв в }
textcolor(2);
if k<=predel then
               begin
               write('!=');
               for i:=k to predel do
               write(f[i])
               end
             else writeln('—Ёб«® ®зҐ­м Ў®«м讥');
writeln;
{‚л室???}
textcolor(1);
writeln('*****************************************');
textcolor(7);
writeln('[Їа®ЎҐ«]-ўл©вЁ  [«оЎ п ¤агЈ п]-Їа®¤®«¦Ёвм');
ch:=readkey;
until ch=' ';
end.


Константа predel если мне не изменят память отвечает за максимальное количество цифр в результате.

Автор: Romtek 11.7.2005, 17:55
Это задача на длинную арифметику. Поиши в поисковике.

Автор: xibyte 12.7.2005, 16:46
Смысл здесь в следующем. Нужен массив каждый элемент которого, соответствует разряду числа, которое должно в итоге получиться. Например число 143 можно представить следующим образом через массив m
m[1]=3 // самый младший разряд
m[2]=4
m[3]=1 // самый старший разряд

Для наглядного примера возведем 2 в 5 степень. Естевственно, что нам нужно 5 раз умножить двойку саму на себя. Т.е. 2^5 = 2*2*2*2*2 = 1*2*2*2*2*2 .Создаем цикл, который будет этим заниматься. Только он будет поочередно умножать каждый разряд на двойку. На первой итерации будем умножать 1*2 следующим образом

m[1]=1 * 2 = 2
m[2]=0 * 2 = 0
m[3]=0 * 2 = 0

На следующей итерации умножаем полученное число 2 опять на 2. Уже получаем 2^2 = 4

m[1]=2 * 2 = 4
m[2]=0 * 2 = 0
m[3]=0 * 2 = 0

Дальше также, получаем 2^3 = 8

m[1]=4 * 2 = 8
m[2]=0 * 2 = 0
m[3]=0 * 2 = 0

А вот дальше ИНТЕРЕСНЕЕ!
Умножаем также каждый разряд на двойку

m[1]=8 * 2 = 16
m[2]=0 * 2 = 0
m[3]=0 * 2 = 0

Первый элемент массива(то есть самый младший разряд) стал равен 16. Такого по определинию быть не может, т.к. разряд - это цифра. Это говорит нам о том, что нужно увеличть следующий разряд. Расскладываем число 16 = 1*10 + 6. В этом разряде мы должны оставить цифру 6. А единицу прибавляем к следующему более старшему разряду.
В алгоритме будем находить эти числа следующим образом
Шестерка - это результат целочисленного деления 16 на 10 (1 = 16 div 10), а шестерка это остаток от деления 16 на 10(6=16 mod 10). Получаем

m[1]=8 * 2 = 6
m[2]=0 * 2 = 0+1
m[3]=0 * 2 = 0

Получили число 16=2^4

Дальше также умножаем каждый разряд на 2

m[1]=6 * 2 = 12
m[2]=1 * 2 = 2
m[3]=0 * 2 = 0

опять в первом разряде опять непорядок, опять расскладываем 12 на еденицу и двойку. Двойку оставляем в первом разряде, а еденицу прибавляем к более старшему. Получаем

m[1]=6 * 2 = 2 = 2
m[2]=1 * 2 = 2+1 = 3
m[3]=0 * 2 = 0 = 0

Получили 2^5. Результатом является массив каждый элемент которого соответствует разряду числа. Печатаем в строчку элементы массива 032, и с начала убераем лишние нули -> 32.

То же самое можно сделать и для 2^500. Только для этого нужно естевственно увеличить размер массива (то есть разрядность конечного числа)
Ниже приведен код программы которая это делает
Код

uses
 crt;
var
 m : array[1..300] of byte;
 stepen, osnova, iter, razryadnost,i,j,slR : integer;
 flag, exitt : boolean;
 f : text;

begin
                                        clrScr;
 stepen := 500;
 osnova := 2;
 iter := 1;
 razryadnost := 300;  {Должно совпадать с количеством элементов массива}
 for i := 2 to razryadnost do m[i] := 0;
 m[1] := 1;
repeat
 for i := razryadnost downto 1 do
  begin
   m[i] := m[i]*osnova;
   j := i;
   repeat
    exitt := true;
    if (m[j] div 10) <> 0 then
    begin
     slR := m[j] div 10;
     m[j] := m[j] mod 10;
     if j <> razryadnost then m[j+1] := m[j+1] +slR;
     exitt := false;
    end;
    inc(j);
   until (j=razryadnost) or exitt;
  end;
 inc(iter);
until (iter = stepen+1);


flag := false;
for i := razryadnost downto 1 do
  if (m[i] <> 0) or flag then
    begin
     write(m[i]);
     flag := true;
    end;

 repeat
 until keypressed;

end.


Надеюсь помог! smile

Автор: Рыська 13.7.2005, 00:29
xibyte, спасибо огромное =)) smile

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)