Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > Задача по паскалю про звёздочки.

Автор: Nix 3.11.2005, 22:59

Всем привет!
помогите решить задачку даны три числа 3-е является суммой 2 первых. Некоторые из цифр чисел заменены звездочкой нужно заминить эти звездочки правильными.
Числа до 250 знаков. Решение вывести минимальное.
Пример
***
***
**2
должно получится
001
001
002
как я понял нужно рассмотреть несколько вариантов растоновки звездочек
|-число 0..9
| * | | * * | *
| | * | * | * *
| | | * | * * *
с первыми 4 случиями понятно а как с остальными?

И как можно реализовать на паскале алгоритм решения линейных уравнениий методом Гауса для 500 уравнений.

Автор: St. Andrew 4.11.2005, 00:48

Меня несколько настораживает сочетание выражений "некоторые цифры заменены звездочками" и "числа до 250 знаков". Если в числе 249 знаков (т.е. цифр) и некоторые из них заменить звездочками, то написание проблемы для общего случая кажется мне задачей вообще труднопостижимой. Может я чего-то недопонимаю... smile

Цитата

Решение вывести минимальное.

Минимальным должно быть само решение или же число какое-то?

Вообще я смысл задачи пока не просек....

Для 500 уравнений ИМХО алгоритм Гаусса реализуется также как и для трех smile

Главное - чтобы память не закончилась. На Си я примеры видел, а вот на паскале - не попадались. В принципе, алгоритм - то там не очень сложный. Нужно только внимательно следить за кучей циклов.

Автор: Guest 4.11.2005, 10:09

St. Andrew
Минимальными должныбыть все числа.
пример
***
***
**2
должно получится
001
001
002

а не
4 4 6
4 4 6
8 9 2
Насчет гауса там память кончается если создавать 500*501 матрицу.
Там поидее нужно использовать другой алгоритм не как для 3.

Автор: St. Andrew 4.11.2005, 11:56

Хорошо, я понял, что минимальными должны быть именно числа. Но все-таки...ведь написано, что числа до 250 знаков! Если бы было все так змечательно, как в твоем примере - дана последняя цифра суммы - то проблем не было бы. Но ведь ты пишешь про "некоторые" цифры, которые заменены звездочками...это как-то бредово, честно говоря. Я не могу себе представить алгоритм, который решает такую неопределенную задачу! Грубо говоря, тут даже количество переменных будет переменным...что-то вообще глухо...

А касательно Гаусса - матрица 500*500 - это примерно 1мб памяти, если речь идет о данных типа integer. В принципе - не так и много. Теоретически можно попробовать использовать динамически выделять память и освобождать ее при отсутствия необходимости в дальнейшем употреблении. Проблема в том, что я алгоритм уже помню несколько смутно smile

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

Автор: Guest 4.11.2005, 13:51

Цитата(St @ 4.11.2005, 11:56)

А касательно Гаусса - матрица 500*500 - это примерно 1мб памяти, если речь идет о данных типа integer. В принципе - не так и много. Теоретически можно попробовать использовать динамически выделять память и освобождать ее при отсутствия необходимости в дальнейшем употреблении.

Но там тип Real и в паскале можно использовать только 250кб динамической памяти тоеть до мегабайта не дотягивает.

Автор: Akina 4.11.2005, 13:59

Цитата(Nix @ 3.11.2005, 23:59)

даны три числа 3-е является суммой 2 первых. Некоторые из цифр чисел заменены звездочкой нужно заминить эти звездочки правильными.
Числа до 250 знаков. Решение вывести минимальное.

Элементарно. Достаточно понять что обрабатывается по 1 разряду от задницы - ибо то что правее не влияет на то что левее, т.к. обработано.

Цитата(Nix @ 3.11.2005, 23:59)

как можно реализовать на паскале алгоритм решения линейных уравнениий методом Гауса для 500 уравнений.

Придется кэшить на диск - но в принципе ничего сложного-то нет... кэшить предлагаю и строки, и столбцы, каждый - в отдельном файле (для 500*500 это 1001 файл). Динамически выделяем буферов по 501 элемент сколько получится и держим таблицу присутствия вектора в памяти - фактически идеология работы со свопом и виртуальной памятью, правда с учетом что любое изменение меняет 2 файла-вектора, а не 1.

Автор: nix 4.11.2005, 14:12

Цитата(Akina @ 4.11.2005, 13:59)

Цитата(Nix @ 3.11.2005, 23:59)

Вот пример
***
***
1992
первя цифра влияет с чего ты начнеш составлять
996
996
1992

Автор: St. Andrew 4.11.2005, 16:12

nix, еще вопросы:
1) Обязательно ли слагаемые должны быть равными?
2) Будут ли некоторые цифры заменены звездочками и в самих слагаемых, а не только в сумме.
Алгоритм рождается в голове, но нужно точно знать условие. Дя твоих приведенных примеров достаточно просто заполнить звездочки в сумме нулями и поделить пополам smile

Но, насколько я понимаю, тут все не так просто...

Автор: nix 4.11.2005, 18:56

St. Andrew
1) нет
2)звездочки могут стоять везде. Могут быть хоть все звёздочки.

Автор: nix 4.11.2005, 23:45

Я зделал задачу про звездочки если надо вот
только осталось проверку зделать можно составить или нет но это легко
извеняюсь что написано плохо(не красиво).

Код


uses crt;
var k,l1,l2,l3,o,i,a,b:byte;
    s1,s2,s3:string;
    f:text;

function ost(e:byte):boolean;
var z,a:byte;
begin
ost:=false;
for z:=e-1 downto 1 do
if  (s1[z]<>'*') and (s2[z]<>'*') and (s3[z]<>'*') then
begin
a:=(ord(s1[z])-48)+(ord(s2[z])-48); if a>9 then a:=a mod 10;
if a<>(ord(s3[z])-48) then begin ost:=true; exit; end else exit;
end
else if  (s1[z]='*') and (s2[z]='*') and (s3[z]='*') then exit
else if (s3[z]='*') then exit
else if  (s1[z]='*') and (s2[z]='*') and (s3[z]<>'9') then exit
else if (s1[z]='*') and (s2[z]<>'*') and (s3[z]<>'*') and (s2[z]<>s3[z]) then begin ost:=true; exit; end
else if (s1[z]<>'*') and (s2[z]='*') and (s3[z]<>'*') and (s1[z]<>s3[z]) then begin ost:=true; exit;
end;
end;

begin
clrscr;
assign(f,'input.pas');
reset(f);
readln(f,s1);
readln(f,s2);
readln(f,s3);
close(f);
l1:=length(s1); l2:=length(s2); l3:=length(s3);
if (l1>l3) or (l2>l3) then writeln('?Ґ«м§п Ї®бва®Ёвм')
else
begin
for i:=l2 to l3-1 do
s2:='0'+s2;
for i:=l1 to l3-1 do
s1:='0'+s1;

o:=0;
for k:=l3 downto 1 do
if (s1[k]<>'*') and (s2[k]<>'*') and (s3[k]<>'*') then o:=((ord(s2[k])-48)+(ord(s1[k])-48))div 10
if (s1[k]='*') and (s2[k]<>'*') and (s3[k]<>'*') then begin
if (ord(s3[k])-48)-o<ord(s2[k])-48 then s1[k]:=chr((10+(ord(s3[k])-48)-o-(ord(s2[k])-48))+48)
else s1[k]:=chr(((ord(s3[k])-48)-o-(ord(s2[k])-48))+48); o:=((ord(s2[k])-48)+(ord(s1[k])-48))div 10; end else

if (s1[k]<>'*') and (s2[k]='*') and (s3[k]<>'*') then begin
if (ord(s3[k])-48)-o<ord(s1[k])-48 then s2[k]:=chr((10+(ord(s3[k])-48)-o-(ord(s1[k])-48))+48)
else s2[k]:=chr(((ord(s3[k])-48)-o-(ord(s1[k])-48))+48); o:=((ord(s2[k])-48)+(ord(s1[k])-48))div 10; end

else if (s1[k]<>'*') and (s2[k]<>'*') and (s3[k]='*') then begin
a:=(ord(s1[k])-48)+(ord(s2[k])-48); if a>9 then a:=a mod 10; s3[k]:=chr(a+48);
o:=((ord(s2[k])-48)+(ord(s1[k])-48))div 10; end else

if (s1[k]='*') and (s2[k]='*') and (s3[k]<>'*') then begin
if ost(k) then a:=10 else a:=0;
a:=(a+(ord(s3[k])-48));
b:=a div 2;
s1[k]:=chr(b+48);
s2[k]:=chr(a-b+48);
o:=((ord(s2[k])-48)+(ord(s1[k])-48))div 10;
end  else

if (s1[k]='*') and (s2[k]<>'*') and (s3[k]='*') then begin
if ost(k) then begin s3[k]:='0'; s1[k]:=chr((10-(ord(s2[k])-48))+48); o:=1; end
else begin s1[k]:='0'; s3[k]:=s2[k]; o:=0; end;

end else

if (s1[k]<>'*') and (s2[k]='*') and (s3[k]='*') then begin
if ost(k) then begin s3[k]:='0'; s2[k]:=chr((10-(ord(s1[k])-48))+48); o:=1; end
else begin s2[k]:='0'; s3[k]:=s1[k]; o:=0; end;
end else

if (s1[k]='*') and (s2[k]='*') and (s3[k]='*') then begin
if ost(k) then begin s1[k]:='5'; s2[k]:='5' end
else begin s1[k]:='0'; s2[k]:='0' end;
s3[k]:='0';
o:=((ord(s2[k])-48)+(ord(s1[k])-48)) div 10;
end;
writeln(s1);
writeln(s2);
writeln(s3);
end;
readkey;
end.

Автор: Akina 4.11.2005, 23:58

Цитата(nix @ 4.11.2005, 15:12)

Вот пример
***
***
1992
первя цифра влияет с чего ты начнеш составлять
996
996
1992

Пример некорректен. Количество разрядов должно быть одинаково во всех 3 операндах.

К тому же не определена до конца исходная задача - что есть "минимальное решение"? когда бОльшее из слагаемых наименьшее из всех возможных? или меньшее - наименьшее? или сумма?

Автор: nix 5.11.2005, 00:04

Цитата(Akina @ 4.11.2005, 23:58)

Цитата(nix @ 4.11.2005, 15:12)

Вот пример
***
***
1992
первя цифра влияет с чего ты начнеш составлять
996
996
1992

Пример какрас коректен с чего это вы взяли что Количество разрядов должно быть одинаково во всех 3 операндах.
Кстати задача решена можете посмотреть в преведущем сообщении.

Автор: St. Andrew 5.11.2005, 02:23

nix, я так и не понял, что именно работает smile

Я сделал файл Input.pas и записал в него:
1*9
*8*
*2*

Программа выдала:
1*9
08*
12*

Это разве то, что ты хочешь получить?

Кстати, согласен с Akina - что именно значит "наименьшее" решение? Тем более, если у тебя разное количество разрядов в числах и все числа разные.
Вспоминается тот факт, что программирование - это в общем-то математическая наука, а компьютер - лишь инструмент для воплощения и проверки алгоритмов. Думаю, что математиков бы решение этой задачи в общем виде не очень порадовало. smile

З.Ы. А к чему вообще эта прога? Программируешь искусственный интелект?

Автор: nix 5.11.2005, 10:15

У меня всё нормально я её немножко потправил провер и потести плиз еще smile

если не сложно до сёднешнего вечера если чё скажите.

Код


uses crt;
var k,l1,l2,l3,o,i,a,b:byte;
    s1,s2,s3,s4:string;
    f:text;

function ost(e:byte):boolean;
var z,a:byte;
begin
ost:=false;
for z:=e-1 downto 1 do
if  (s1[z]<>'*') and (s2[z]<>'*') and (s3[z]<>'*') then
begin
a:=(ord(s1[z])-48)+(ord(s2[z])-48); if a>9 then a:=a mod 10;
if a<>(ord(s3[z])-48) then begin ost:=true; exit; end else exit;
end
else if  (s1[z]='*') and (s2[z]='*') and (s3[z]='*') then exit
else if (s3[z]='*') then exit
else if  (s1[z]='*') and (s2[z]='*') and (s3[z]<>'9') then exit
else if (s1[z]='*') and (s2[z]<>'*') and (s3[z]<>'*') and (s2[z]<>s3[z]) then begin ost:=true; exit; end
else if (s1[z]<>'*') and (s2[z]='*') and (s3[z]<>'*') and (s1[z]<>s3[z]) then begin ost:=true; exit;
end;
end;

procedure prov;
var i,o:byte;
begin
o:=0;
s4:=s3;
for i:=l3 downto 1 do
begin
s4[i]:=chr((((ord(s1[i])-48)+o+(ord(s2[i])-48)) mod 10)+48);
o:=((ord(s2[i])-48)+(ord(s1[i])-48)+o)div 10;
end;
if s4<>s3 then begin writeln('Ґ«м§п Ї®бва®Ёвм');{ exit;} end;
writeln(s1);
writeln(s2);
writeln(s3);
end;

begin
clrscr;
assign(f,'input.pas');
reset(f);
readln(f,s1);
readln(f,s2);
readln(f,s3);
close(f);
l1:=length(s1); l2:=length(s2); l3:=length(s3);
if (l1>l3) or (l2>l3) then writeln('?Ґ«м§п Ї®бва®Ёвм')
else
begin
for i:=l2 to l3-1 do
s2:='0'+s2;
for i:=l1 to l3-1 do
s1:='0'+s1;

o:=0;
for k:=l3 downto 1 do

if (s1[k]<>'*') and (s2[k]<>'*') and (s3[k]<>'*') then o:=((ord(s2[k])-48)+(ord(s1[k])-48)+o)div 10
else

if (s1[k]='*') and (s2[k]<>'*') and (s3[k]<>'*') then begin
if (ord(s3[k])-48)-o<ord(s2[k])-48 then s1[k]:=chr((10+(ord(s3[k])-48)-o-(ord(s2[k])-48))+48)
else s1[k]:=chr(((ord(s3[k])-48)-o-(ord(s2[k])-48))+48); o:=((ord(s2[k])-48)+(ord(s1[k])-48)+o)div 10; end else

if (s1[k]<>'*') and (s2[k]='*') and (s3[k]<>'*') then begin
if (ord(s3[k])-48)-o<ord(s1[k])-48 then s2[k]:=chr((10+(ord(s3[k])-48)-o-(ord(s1[k])-48))+48)
else s2[k]:=chr(((ord(s3[k])-48)-o-(ord(s1[k])-48))+48); o:=((ord(s2[k])-48)+(ord(s1[k])-48)+o)div 10; end

else if (s1[k]<>'*') and (s2[k]<>'*') and (s3[k]='*') then begin
a:=(ord(s1[k])-48)+(ord(s2[k])-48); if a>9 then a:=a mod 10; s3[k]:=chr(a+48);
o:=((ord(s2[k])-48)+(ord(s1[k])-48)+o)div 10; end else

if (s1[k]='*') and (s2[k]='*') and (s3[k]<>'*') then begin
if ost(k) then
a:=10 else a:=0;
a:=(a+(ord(s3[k])-48))-o;
b:=a div 2;
if a=19 then dec(a);
s1[k]:=chr(b+48);
s2[k]:=chr(a-b+48);
o:=((ord(s2[k])-48)+(ord(s1[k])-48)+o)div 10;
end else

if (s1[k]='*') and (s2[k]<>'*') and (s3[k]='*') then begin
if ost(k) then begin s3[k]:='0'; s1[k]:=chr((10-o-(ord(s2[k])-48))+48); o:=1; end
else begin s1[k]:='0'; s3[k]:=chr((((ord(s2[k])-48)+o) mod 10)+48); o:=0; end;

end else

if (s1[k]<>'*') and (s2[k]='*') and (s3[k]='*') then begin
if ost(k) then begin s3[k]:='0'; s2[k]:=chr((10-o-(ord(s1[k])-48))+48); o:=1; end
else begin s2[k]:='0'; s3[k]:=chr((((ord(s1[k])-48)+o) mod 10)+48); o:=0; end;
end else

if (s1[k]='*') and (s2[k]='*') and (s3[k]='*') then begin
if ost(k) then begin s1[k]:='5'; s1[k]:=chr((ord(s1[k])-48-o)+48); s2[k]:='5' end
else begin s1[k]:='0'; s2[k]:='0' end;
s3[k]:='0';
o:=((ord(s2[k])-48)+(ord(s1[k])-48)+o) div 10;
end;
prov;
end;
readkey;
end.

Цитата

А к чему вообще эта прога? Программируешь искусственный интелект?

Нет просто готовлюсь к олимпиаде.

Цитата

"наименьшее" решение.

Это к примеру нам дано
***1
***1
***2
надо вывести
0001
0001
0002
а не к примеру
4441
5551
9991
тоесть если есть несколько вариантов постоновки чисел то выбираем наименьшее.

Автор: St. Andrew 5.11.2005, 12:19

nix Сейчас - все нормально работает! Кстати, выровнять все числа по количеству разрядов - хорошая мысль! Меня все тянуло уменьшать количество знаков в наибольшем, а ты просто увеличил их число в более коротких числах! Молодец! smile

Кстати, для справки - ты обрабатываешь разряды чисел, начиная с левой стороны или с правой?

Автор: nix 5.11.2005, 13:47

Цитата(St @ 5.11.2005, 12:19)

nix Кстати, для справки - ты обрабатываешь разряды чисел, начиная с левой стороны или с правой?

С правой.