Форум программистов, компьютерный форум, киберфорум
Turbo Pascal
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
0 / 0 / 0
Регистрация: 26.03.2013
Сообщений: 12
1

Фальшивомонетчики!

26.03.2013, 19:49. Показов 761. Ответов 5
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Фальшивомонетчики.
Один очень неграмотный и неопытный фальшивомонетчик напечатал купюры достоинством а1, а2,..аN и пошел в магазин. Однако владелец магазина тоже оказался фальшивомонетчиком, так что в кассе магазина были купюры достоинством b1,b1,..bN. Получиться ли у фальшивомонетчика-покупателя купить товар стоимостью Х рублей? Сделка считается состоявшейся, если покупатель и продавец смогли полностью рассчитаться.

Формат входных данных.
В первой строке записана сумма сделки Х, во второй - кол-во купюр N у покупателя, затем числа а1,а2..аN по одному в строке, затем - кол-во купюр M у продавца и числа b1,b2,..bN (достоинство каждой купюры не превышает 1000, N<50, M<50. Все числа в задаче предполагаются целыми.

Формат выходных данных.
Выводиться значение "1", если сделка возможна и "0" - в противном случае.

Пример
Входные данные
7 - сумма сделки
3 - кол-во купюр у покупателя
3, 5, 6 - достоинство купюр у покупателя
2 - кол-во купюр у продавца
4, 5 - достоинство купюр у продавца
Выходные данные
1 - сделка совершена

Пример
Входные данные
10 - сумма сделки
4 - кол-во купюр у покупателя
2, 3, 3, 6 - достоинство купюр у покупателя
3 - кол-во купюр у продавца
5, 6, 7 - достоинство купюр у продавца
Выходные данные
0 - сделка не совершена
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.03.2013, 19:49
Ответы с готовыми решениями:

Фальшивомонетчики.
Фальшивомонетчики. Один очень неграмотный и неопытный фальшивомонетчик напечатал купюры...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
142 / 148 / 116
Регистрация: 15.11.2012
Сообщений: 537
Записей в блоге: 2
26.03.2013, 21:44 2
по-моему это очень непростая задача и в какой-нибудь книжке по комбинаторике наверняка рассматриваются подобные
0
50 / 50 / 41
Регистрация: 20.08.2012
Сообщений: 123
26.03.2013, 23:40 3
Первой мыслью было составить массив, значения в котором - это разница между ценой товара и банкнотами продавца (то есть возможные варианты сдачи), а затем перебирать варианты "цена минус банкноты покупателя", до первого совпадения полученного значения с любым значением из первого массива, но если все это дело хранить, то при 50 банкнотах количество возможных сумм ну ооочень велико (факториал 50, по-моему). Это и правда задача какая-то больше комбинаторная, а будет алгоритм - реализация на паскале не должна серьёзных трудностей вызвать
0
142 / 148 / 116
Регистрация: 15.11.2012
Сообщений: 537
Записей в блоге: 2
27.03.2013, 09:01 4
да, наверняка есть самый рациональный алгоритм уже составленный.
даже если у человека 5 банкнот то перебором всех вариантов будут:
12 13 14 15 23 24 25 34 35 45
123 124 125 134 135 145 234 235 245 345
1234 1235 2345
12345
Скорее всего это решается вложенными циклами
0
0 / 0 / 0
Регистрация: 26.03.2013
Сообщений: 12
02.04.2013, 21:11  [ТС] 5
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
Program zach;
uses crt;
var
a:array[1..50] of 1..1000;
a1:array[1..10000] of integer;
b:array[1..50] of 1..1000;
b1:array[1..10000] of integer;
l,j,s,x,i,n,m:integer;
q,ss,k,w:longint;
begin
clrscr;
writeln('Vvedite symmy:');
readln(x);
writeln('Vvedite kolichestvo monet pokypatila:');
readln(n);
writeln('Vvedite ih dostoinstvo:');
for i:=1 to n do readln(a[i]);
writeln('Vvedite kolichestvo monet prodavca:');
readln(m);
writeln('Vvedite ih dostoinstvo:');
for i:=1 to m do readln(b[i]);
i:=1;j:=1;
while (s<>x) and (j<>n) do begin
while (s<x) and (i<=n) do begin
s:=s+a[i];i:=i+1;end;
if (s>x) and (i-1<>n) then s:=s-a[i-1];
if (i-1=n) and (s<>x) then begin j:=j+1; i:=j; s:=0; end;
end;
if s=x then write('1') else begin
for i:=1 to n do begin
s:=0;
for j:=i to n do begin s:=s+a[j];
if s>x then begin k:=k+1; a1[k]:=s-x;end;
end;
end;
for i:=1 to m do begin
s:=0;
for j:=1 to m-1 do begin s:=s+b[j]; w:=w+1; b1[w]:=s;end;
end;
ss:=1;q:=1;
while ss<>k do begin
while q<>w do begin
if a1[k]=b1[w] then l:=1;
q:=q+1;
end;
ss:=ss+1;q:=1;
end;
write('Otvet:',l);
end;
readkey;
end.
Фальшивомонетчики.
Один очень неграмотный и неопытный фальшивомонетчик напечатал купюры достоинством а1, а2,..аN и пошел в магазин. Однако владелец магазина тоже оказался фальшивомонетчиком, так что в кассе магазина были купюры достоинством b1,b1,..bN. Получиться ли у фальшивомонетчика-покупателя купить товар стоимостью Х рублей? Сделка считается состоявшейся, если покупатель и продавец смогли полностью рассчитаться.

Формат входных данных.
В первой строке записана сумма сделки Х, во второй - кол-во купюр N у покупателя, затем числа а1,а2..аN по одному в строке, затем - кол-во купюр M у продавца и числа b1,b2,..bN (достоинство каждой купюры не превышает 1000, N<50, M<50. Все числа в задаче предполагаются целыми.

Формат выходных данных.
Выводиться значение "1", если сделка возможна и "0" - в противном случае.

Пример
Входные данные
7 - сумма сделки
3 - кол-во купюр у покупателя
3, 5, 6 - достоинство купюр у покупателя
2 - кол-во купюр у продавца
4, 5 - достоинство купюр у продавца
Выходные данные
1 - сделка совершена

Пример
Входные данные
10 - сумма сделки
4 - кол-во купюр у покупателя
2, 3, 3, 6 - достоинство купюр у покупателя
3 - кол-во купюр у продавца
5, 6, 7 - достоинство купюр у продавца
Выходные данные
0 - сделка не совершена
0
142 / 148 / 116
Регистрация: 15.11.2012
Сообщений: 537
Записей в блоге: 2
14.04.2013, 23:15 6
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
Program vyborki;
uses crt;
Type TArrByte=Array[1..100]Of Byte;
     TArrInt=Array[1..100]Of Integer;
Var
   A,B:TArrInt;
   flag1,flag2:TArrByte;
   i,n,m:integer; Resh:boolean;
   SumPok,SumProd,Tsena,Sdacha:Integer;
 
{}Function proverka(Var flag:TArrByte):Boolean;
Var i:Integer; f:Boolean;
Begin f:=False;
      For i:=1 To N Do If flag[i]=0 Then F:=True;
      proverka:=F; End;
 
{}Procedure Variant(Var flag:TArrByte; Var Arr:TArrInt; Var Sum:Integer);
Var i,j:Integer;
Begin i:=1;
      While (flag[i]=1)and(i<=n) Do i:=i+1;
      If i<=n Then Begin
         flag[i]:=1;
         For j:=1 To i-1 Do flag[j]:=0;
      End;
      Sum:=0;
      For i:=1 To n Do If flag[i]=1 Then Sum:=Sum+Arr[i];
End;
 
{}Procedure Sravnenie;
Begin If SumPok=Tsena Then Resh:=True; End;
 
BEGIN
clrscr; Resh:=False;
Assign(input,'dengi.txt'); Reset(input);
Readln(Tsena); Readln(n);
For i:=1 To n Do Begin
    read(A[i]);
    flag1[i]:=0;
End;
Readln(m);
For i:=1 To m Do Begin
    read(B[i]);
    flag2[i]:=0; End;
While proverka(flag1) Do Begin
      Variant(flag1,A,SumPok);
      If SumPok<Tsena Then Continue;
      If SumPok=Tsena Then Begin
         For i:=1 To n Do If flag1[i]=1 Then Write(A[i],'+');
         Write('='); Write(Tsena); Resh:=true;
      End;
      If SumPok>Tsena Then Begin
         Sdacha:=SumPok-Tsena;
         For i:=1 To n Do flag2[i]:=0;
         While proverka(flag2) Do Begin
               Variant(flag2,B,Sumprod);
               If SumProd=Sdacha Then Begin
                  For i:=1 To n Do If flag1[i]=1 then write(A[i],'+');
                  Writeln('=',SumPok,' (pokupatel)');
                  For i:=1 To m Do
                      If flag2[i]=1 Then Write(B[i],'+');
                      Writeln('=',Sdacha,' (prodavec)');Writeln;
                  Resh:=True;
                  Break;
               End;
         End;
      End;
End; If Not Resh Then Writeln('resheniy net!');
END.
подобная задача рассматривается, например, в книжке "Потопахин - решение сложных задач". Называется это выборками, и основная суть там что параллельно с массивом чисел(банкноты) ведётся массив, в котором с помощью двоичного перебора рассматриваются все неповторяющиеся комбинации. Я взял рассмотренную там задачу, и добавил такой момент, что всякий раз когда выборка у "покупателя" становится больше чем "сумма сделки", то включается внутренний цикл, в котором расматриваются все выборки "продавца" и сравниваются с разницей между текущей выборкой покупателя и суммой сделки.
0
14.04.2013, 23:15
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru