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

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

Форум программистов > Центр помощи > [Алгоритм] I=A*K+B*L

Автор: KasMP 17.11.2007, 19:26

Здравствуйте, товарищи программисты! smile

Проходим Паскаль, контрольная по теме "Функции". У меня проблема не в паскале, а в самом алгоритме. smile

Задачка звучит так: smile

Цитата

По заданным натуральным числам A, B, N среди чисел, не превосходящих N, указать такие I, которые представимы как I=K*A+L*B, где K и L - целые неотрицательные числа.

Взгляните, пожалуйста, на мой набросочек и скажите, какие мысли smile

вас посетили...

Код

{В начале нужно выяснить, превосходит N число A (B) или нет.
Чтобы предусмотреть все случаи,
мы должны включить в программу 3 таких сравнения.}
function SravN (ab, n: integer): boolean;
    begin
    if ab<=n then SravN:=true else SravN:=false;
    end;

{Если A (B) уже превосходит N,
то для поиска I будем использовать только B (A).}
procedure AorB (ab, n: integer);
    var    k, i: integer;
    begin
    k:=2; i:=ab;
    repeat
        write (' ', i);
        i:=ab*k;
        inc (k);
    until i>n
    end;

var    a, b, n: integer;
    k, l: integer;


begin

{По условию K и L могут одновременно равняться нулю.
А это значит, что всегда будет существовать I=A*0+B*0=0.}
writeln ('0');

if SravN(a,n) then do
    {Теперь уже известно, что N больше A.
    Нужно узнать, превосходит N число B или нет.
    Используем созданную для этого функцию.}
    if SravN(b,n) then do {для поиска I используем и A, и B}
        begin
        {Не знаю, как сделать оптимально. Помогите, пожалуйста!}
        end
    else {для поиска I используем только A} do AorB(a,n)
else    {Теперь уже известно, что A больше N.
    Нужно узнать, превосходит N число B или нет.
    Используем созданную для этого функцию.}
    if SravN(b,n) then do {для поиска I используем только B} AorB(b,n);


readln;
end.

Заранее благодарю уже за внимание! smile

Автор: KasMP 17.11.2007, 19:29

Здравствуйте, товарищи программисты! smile

Проходим Паскаль, контрольная по теме "Функции". У меня проблема не в паскале, а в самом алгоритме. smile

Задачка звучит так: smile

Цитата

Взгляните, пожалуйста, на мой набросочек и скажите, какие мысли smile

вас посетили...

Код

{В начале нужно выяснить, превосходит N число A (B) или нет.
Чтобы предусмотреть все случаи,
мы должны включить в программу 3 таких сравнения.}
function SravN (ab, n: integer): boolean;
    begin
    if ab<=n then SravN:=true else SravN:=false;
    end;

{Если A (B) уже превосходит N,
то для поиска I будем использовать только B (A).}
procedure AorB (ab, n: integer);
    var    k, i: integer;
    begin
    k:=2; i:=ab;
    repeat
        write (' ', i);
        i:=ab*k;
        inc (k);
    until i>n
    end;

var    a, b, n: integer;
    k, l: integer;


begin

{По условию K и L могут одновременно равняться нулю.
А это значит, что всегда будет существовать I=A*0+B*0=0.}
writeln ('0');

if SravN(a,n) then do
    {Теперь уже известно, что N больше A.
    Нужно узнать, превосходит N число B или нет.
    Используем созданную для этого функцию.}
    if SravN(b,n) then do {для поиска I используем и A, и B}
        begin
        {Не знаю, как сделать оптимально. Помогите, пожалуйста!}
        end
    else {для поиска I используем только A} do AorB(a,n)
else    {Теперь уже известно, что A больше N.
    Нужно узнать, превосходит N число B или нет.
    Используем созданную для этого функцию.}
    if SravN(b,n) then do {для поиска I используем только B} AorB(b,n);


readln;
end.

Заранее благодарю уже за внимание! smile

Автор: esperant0 17.11.2007, 19:43

Раздел по алгоритмам. А у вас вопрос по анализу кода?

Ничего не понимаю

Автор: KasMP 17.11.2007, 19:59

esperant0, возможно, моя низкая квалификация дала о себе знать... Не судите строго студента.
Но вообще я имела в виду, что не могу составить часть алгоритма. В коде это место записано так:

Цитата

begin
{Не знаю, как сделать оптимально. Помогите, пожалуйста!}
end

А сам код приведен для того, чтобы вы могли оценить рациональность других частей алгоритма.

Кстати, спасибо за попытку понять!

Автор: primax 18.11.2007, 20:20

Я не совсем понимаю условие задачи.
Зачем искать I по числам А или B раздельно, когда у тебя одно из этих чисел больше N? Ведь если К, L>0, то при A, B>N (одно из них или два сразу, без разницы) I>N полюбому. Я в условии не заметил ничего что мне бы говорило о раздельном поиске, сказано четко: I=K*A+L*B
Если нужно организовать проверку на то что меньше, то я бы делал так:

Код


{Функция возвращается всегда истину, пока не докажет противоположное}
function ABvsN(a,b,n:integer):boolean;
  begin
     ABvsN:=true;
     if (a>n)or(b>n) then ABvsN:=false;
  end;

А дальше, как по мне, самый простой вариант, это 2 вложеных логических цикла (вайл, репит) с проверкой "не проскочили ли мы условие I<N" и поочередным инкрементом L,K. Т.е. фактически тебе нужно организовать полный перебор выражения I=K*A+L*B используя твои условия по переменым K,L и константам A,B (константы - переменые которые не меняются на данном этапе, а не переменые-константы smile

).
Но тут еще нюанс есть: А,В тоже должны быть больше 0. Иначе там просто вариантов бесконечность вариантов.
Реализовал как я понял.

Код


function ABvsN(a,b,n:integer):boolean;
  begin
     ABvsN:=true;
     if (a>n)or(b>n)or(b<0)or(a<0) then ABvsN:=false;
  end;
{I:=K*A+L*B}
var a,b,n,k,l,i:integer;
begin
  read(a,b,n);
  k:=0;l:=0;i:=0;
  if abvsn(a,b,n) then
     while I<N do begin
       while I<N do begin
         writeln(k,',',l,' | ',i); {выводит в форме: k,l | результат, используя эти значения}
         inc(l);
         i:=k*a+l*b;
         end;
       l:=0;
       inc(k);
       i:=k*a+l*b;
     end;
end.

Если я не так понял все в итоге) То уточни условие конкретнее.
Кстати, часные случаи желательно писать в самом алгоритме, а не отдельно, но если это конечно не увеличит масивность программы или кол-ва вычислений лишних.
П.С. 17 число :О День студента ж ведь, какие могут быть дела))
Извини если с объяснениями запутал.

Добавлено через 2 минуты и 33 секунды
Можно убрать 3 присваевания, если поставишь 10 строку под 11 добавив begin и end для IF.

Автор: KasMP 24.11.2007, 00:40

Цитата(primax @ 18.11.2007, 20:20

)

Зачем искать I по числам А или B раздельно, когда у тебя одно из этих чисел больше N?

Чтобы использовать функции... (задание по этой теме)

Цитата(primax @ 18.11.2007, 20:20

)

Ведь если К, L>0, то при A, B>N (одно из них или два сразу, без разницы) I>N полюбому.

Бесспорно, это так smile

. Только по условию K и L просто неотрицательные (т.е. могут равняться нулю...).

Автор: KasMP 24.11.2007, 01:18

Пожалуйста, посмотрите на плод моих трудов, суть которого сводится к следующему:

по условию K и L могут равняться нулю; а это значит, что всегда будет существовать I=A*0+B*0=0; поэтому всегда в самом начале будем выводить "0";
если A (или B) уже превосходит N, то при любом K>0 (или L>0) мы получим I>N (т.е. I, неудовлетворяющее условию); поэтому если A>N (или B>N), то изменять можно только коэффициент перед B (A или ), т.е. L ( или K), а коэффициент K (или L) всегда должен равняться нулю.
- чтобы рассмотреть все случаи отношений A и B к N, использовать в программе функции, удобно организовать функцию сравнения числа с N;
- чтобы использовать процедуры (все равно они схожи с функциями) и оптимизировать программу, удобно создать процедуру поиска I с помощью или A, или B.
если ни A, ни B не превосходят N, то тогда мы сначала ищем I только с помощью A (L=0), затем только с помощью B (K=0) (надо же почаще использовать процедуры!!), а после с помощью A и B.
(для поиска по A и B создаем отдельную процедуру: внешний цикл с итерацией по K, вложенный в него цикл с итерацией по L и выводом полученных значений I с разложением)
если и A, и B превосходят N, то тогда условию задачи будет удовлетворять только I=0 (выведенное в самом начале).

Скажите, рационален ли мой алгоритм и т.п.? Можно ли что-то улучшить?

Код

{В начале нужно выяснить, превосходит N число A (B) или нет.
Чтобы предусмотреть все случаи,
мы должны включить в программу 3 таких сравнения.}
function SravN (ab, n: integer): boolean;
    begin
    if ab<=n then SravN:=true else SravN:=false;
    end;

{Если A (B) уже превосходит N,
то для поиска I будем использовать только B (A).}
procedure AorB (ab, n:integer; c, nc: char);
    {Символьные переменные "c" и "nc" будем использовать для того,
    чтобы при выведении разложения на множители пользователь мог увидеть,
    какое число (А или В) используется для поиска I, а какое - нет.}
    var    k, i: integer;
    begin
    k:=1; i:=ab;
    writeln ('Для поиска I используем ', c, ':');
    repeat
        writeln (i, '=', k, c, '+0', nc, ' (', i, '=', k, '*', ab, ').');
        inc (k);
        i:=ab*k;
    until i>n;
    writeln;
    end;

{Если и А, и В не превосходят N,
то для поиска I будем использовать и А, и В.}
procedure AandB (a, b, n: integer);
    var     i, k, l, y, z: integer;
    begin
    writeln ('Для поиска I используем и A, и B:');
    k:=1; l:=1; z:=a*k; i:=z+b*l;
    while z<n do begin
        y:=n-b;
        repeat
            writeln (i, '=', k, 'A+', l, 'B (', i, '=', k, '*', a, '+', l, '*', b, ').');
            {в данном подцикле просто увеличиваем множитель L на единицу;
            (и, соответственно, число I увеличивается на B);
            на мой взгляд, все это лучше (быстрее, экономнее)
            сделать не так (l:=l+1; i:=a*k+b*l), а так:}
            inc (i, b); inc (l);
            until i>y;
        {теперь производим аналогичное действие во внешнем цикле:
        увеличиваем множитель К на единицу, тем самым увеличивая I
        (вернее, Z=A*K, водящее в состав I) на A}
        inc (k); inc (z, a);
        {не забываем "обнулить" значение множителя подцикла L
        (присваиваем единицу, т.к. за значения I при множителе,
        равном нулю, отвечает процедура AorB)
        и "обнулить" значение числа I}
        l:=1; i:=z+b*l;
        end;
    end;


{Итак, наконец-то завершено создание процедур и функций,
приступаем непосредственно к самой программе.}

var    a, b, n: integer;
    k, l: integer;


begin

writeln ('Пожалуйста, введите натуральные A, B и N:');
readln (a, b, n);

writeln ('Для заданных A=', a, ', B=', b, ' и N=', n, '  найдены следующие значения I: ');

{По условию K и L могут одновременно равняться нулю.
А это значит, что всегда будет существовать I=A*0+B*0=0.}
writeln ('0=0A+0B (0=0*', a, '+0*', b, ').'); writeln;

if SravN(a,n) then
    {Теперь уже известно, что N больше A.
    Нужно узнать, превосходит N число B или нет.
    Используем созданную для этого функцию.}
    if SravN(b,n) then {для поиска I используем и A, и B} begin
            AorB(a,n,'A','B');
            AorB(b,n,'B','A');
            AandB(a,b,n);
            end
        else {для поиска I используем только A} AorB(a,n,'A','B')
else    {Теперь уже известно, что A больше N.
    Нужно узнать, превосходит N число B или нет.
    Используем созданную для этого функцию.}
    if SravN(b,n) then {для поиска I используем только B} AorB(b,n,'B','A');

{Если же и A, и B превосходят N (а именно этот случай оказался бы на месте
if Sravn(a,n) then ... else
    if Sravn(b,n) then ... else [!]случай,  о котором речь[!]),
то заданному условию удовлетворяет единственное сочетание K и L,
рассмотренное в самом начале программы: K=0, L=0; I=A*0+B*0=0.}

readln;
end.

Спасибо за внимание!

Добавлено через 4 минуты и 43 секунды
Вот только незадача: если A=3, B=4, N=21, то программа выводит и I=22...
Как вовремя остановить цикл? smile

Автор: GIK 24.11.2007, 12:42

Цитата

Вобщем то понятно, но пониманий складывается уж очень много... Где предел числе? и у A, B, N и у K c L ?

Разьясни задачу подробнее и тебе помогут

Автор: mr.Anderson 24.11.2007, 15:48

Цитата

Вобщем то понятно, но пониманий складывается уж очень много... Где предел числе? и у A, B, N и у K c L ?

Давайте попробую объяснить.

1. Предел чисел A и B - можно взять беззнаковое целое, скажем, Word (я по паскалю мыслю), плюс учитываем, что они не превышают N.

2. Насчет предела K и L. Поскольку в формуле используется умножение этих чисел на два данных, плюс известно, что они неотрицательные (скажем, тот же тип Word), то складывается следующая мысль: поскольку числа A, B не могут быть отрицательными и не могут быть нулевыми (нуль в натуральные не входит, напомню), то:

Если оба числа равны 1, то K и L могут быть не более I/2. Например, 4 = 2х1 + 2х1. Соответственно, вот вам первый предел.
Если какое-то число из A и B (или оба сразу) не равны единице, то пределы для чисел K и L можно рассчитать по формуле I/2*A и I/2*B соответственно.

Отсюда и пляшем с алгоритмом. Если не получится, я постараюсь помочь.

Автор: GIK 24.11.2007, 16:16

Спасибо конечно, но пропуская через цикл эти занчения, явно какой-то предел (100 или 100 000 например) должен существовать smile

До какого числа диапазоны выстраивать?

Автор: mr.Anderson 24.11.2007, 18:32

Дык. А я о чем речь вел? Вот алг (не проверял, правда...):

Код


...
var
 k, l: Word;
 i, j: Word;
 ctrl: Boolean;
...
k := 0;
l := 0;
ctrl := false;

for i:=1 to I/2*A do
 for j:=1 to I/2*B do
 begin
  if( i*A + j*B ) = I then
  begin
   k := i;
   l := j;
   ctrl := true;
   break;
  end;
 end;

if( ctrl ) then
 writeln( 'K = ', k, ', L = ', l )
else writeln( 'No solutions!' );

Автор: primax 25.11.2007, 02:47

Цитата(KasMP @ 24.11.2007, 00:40

)

Бесспорно, это так smile . Только по условию K и L просто неотрицательные (т.е. могут равняться нулю...).

Не заметил этого в условии изложеным тобой smile

Цитата(KasMP @ 24.11.2007, 00:40

)

Чтобы использовать функции... (задание по этой теме)

Хм. Задание реализовать программу используя подпрограммы (функции в даном случае)? или задание в том чтобы реализовать функции раздельного поиска (ну т.е. то что ты делала smile

)?

В принципе могу завтра, если будет время, твою задачку доделать используя твою логику (т.е. твою задумку для достижения результата).

П.С. Кстати, там можно в 2 раза уменьшить сложно алгоритма (я про свой), если заметить что там после определеного момента идут симметричные результаты (вроде было так, не помню, неделю назад это заметил). smile

Автор: KasMP 26.11.2007, 16:57

Цитата(GIK @ 24.11.2007, 12:42

)

Вобщем то понятно, но пониманий складывается уж очень много... Где предел числе? и у A, B, N и у K c L ?

Уточню у преподавателя smile

Цитата(mr.Anderson @ 24.11.2007, 15:48

)

1. Предел чисел A и B - можно взять беззнаковое целое, скажем, Word (я по паскалю мыслю), плюс учитываем, что они не превышают N.

2. Насчет предела K и L. Поскольку в формуле используется умножение этих чисел на два данных, плюс известно, что они неотрицательные (скажем, тот же тип Word), то складывается следующая мысль: поскольку числа A, B не могут быть отрицательными и не могут быть нулевыми (нуль в натуральные не входит, напомню), то:

* Если оба числа равны 1, то K и L могут быть не более I/2. Например, 4 = 2х1 + 2х1. Соответственно, вот вам первый предел.
* Если какое-то число из A и B (или оба сразу) не равны единице, то пределы для чисел K и L можно рассчитать по формуле I/2*A и I/2*B соответственно.

Вроде так...

Цитата(mr.Anderson @ 24.11.2007, 15:48

)

Отсюда и пляшем с алгоритмом.

Куда?

Какое отношение к нашему алгоритму имеют эти общие формулы пределов? smile

(неужели я вообще ничего не понимаю? smile

)

Цитата(mr.Anderson @ 24.11.2007, 15:48

)

Если не получится, я постараюсь помочь.

Будьте добры!! smile

Цитата(GIK @ 24.11.2007, 16:16

)

До какого числа диапазоны выстраивать?

Думаю, навряд ли имеет смысл брать слишком большие числа: проверить будет сложно. Имхо преподаватель, отвечая на мой вопрос, ограничится числом 100 (а на практике, скорее всего, не поднимется выше 50-60...).

Вобщем, предел(A)=предел(B)=предел(N)=100 smile

Цитата(mr.Anderson @ 24.11.2007, 18:32

)

Дык. А я о чем речь вел? Вот алг (не проверял, правда...):

Мне не удалось проникнуться его сутью. К чему все это?

Вновь благодарю за прочтение моего полуламерского опуса. smile

Автор: KasMP 26.11.2007, 17:49

Цитата(primax @ 25.11.2007, 02:47

)

Не заметил этого в условии изложеным тобой

"... где K и L - целые неотрицательные числа."

Цитата(primax @ 25.11.2007, 02:47

)

Первое.

Цитата(primax @ 25.11.2007, 02:47

)

В принципе могу завтра, если будет время, твою задачку доделать используя твою логику (т.е. твою задумку для достижения результата).

Нет, это моя задачка, она МОЯ, я хочу сама, не надо делать за меня, я просто прошу совет!!!!!!!

Автор: Akina 26.11.2007, 18:46

ну и чего? берем и считаем:

A
A+B
A+2B
A+3B...
...
A+mB
2A
2A+B
2A+2B
2A+3B...
...
2A+nB
3A
3A+B
...
pA+qB
...
НОК(A,B)

строки отсечки, помеченные жирно - это те, после которых следующая строка выскочит за пределы N. Если НОК(A,B)<N, то в момент рассчета НОК(A,B) все бОльшие этого значения представимые числа уже выведены ранее.

Добавлено @ 18:51
В частности, легко доказать, что любое число, превышающее НОК(A,B) и делащееся на НОД(A,B), представимо в виде K*A+L*B, и соответственно если они взаимно просты (НОД=1), то любое число, превышающее A*B, представимо в виде K*A+L*B.

Автор: primax 26.11.2007, 19:26

Цитата(KasMP @ 26.11.2007, 17:49)

Цитата(primax @ 25.11.2007, 02:47

)

Не заметил этого в условии изложеным тобой

"... где K и L - целые неотрицательные числа."

Ой, я говорил про А, В... ведь мы ищем представления I прежде задав A, B, а если А, В (ух блин) < 0 то представлений I будет просто уйма.
По условию (фраза "не превосходящих") I<N, а если одно из тех чисел отризательно то это условие выполняется всегда. Например: A>0, B<0 ==> K=const, L стремится к бесконечности ==> I стремится к минус бесконечности. Хотя это не особо важно.

Цитата(KasMP @ 26.11.2007, 17:49

)

Нет, это моя задачка, она МОЯ, я хочу сама, не надо делать за меня, я просто прошу совет!!!!!!!

Извини, просто за последнее время много чего по этому поводу проскочило, кто-то просит решение, кто-то консультацию и прочее-прочее....

Совет по той части которая у тебя пропущена (поиск для А и В одновременно, моя предложеная реализация выше):

Цитата(primax @ 18.11.2007, 20:20

)

самый простой вариант, это 2 вложеных логических цикла (вайл, репит) с проверкой "не проскочили ли мы условие I<N" и поочередным инкрементом L,K. Т.е. фактически тебе нужно организовать полный перебор выражения I=K*A+L*B используя твои условия по переменым K,L и константам A,B (константы - переменые которые не меняются на данном этапе, а не переменые-константы smile ).

Автор: KasMP 27.11.2007, 00:07

Цитата(Akina @ 26.11.2007, 18:46

)

ну и чего? берем и считаем:

Взгляни(те), пожалуйста, вот на http://forum.vingrad.ru/forum/topic-182398.html тему smile

Цитата(Akina @ 26.11.2007, 18:46

)

все бОльшие этого значения представимые числа уже выведены ранее.

Вообще, судя по всему, стоит сказать, что был разговор на тему того, допустим ли вывод одних и тех же чисел (например, А=2 и В=4; тогда 2*4+4*2=2*2+4*3=16); после некоторых раздумий преподаватель пришел к выводу, что допустим (и даже в некотором смысле желателен), но только в том случае, когда пользователь сможет увидеть разложение на множители (что и реализовано в указанной выше теме).
______________________________________________________

Цитата(primax @ 26.11.2007, 19:26

)

По условию (фраза "не превосходящих") I<N, а если одно из тех чисел отризательно то это условие выполняется всегда. Например: A>0, B<0 ==> K=const, L стремится к бесконечности ==> I стремится к минус бесконечности. Хотя это не особо важно.

Нет

. В условии сказано: "По заданным натуральным числам A, B и N...".

Цитата(primax @ 26.11.2007, 19:26

)

Извини, просто за последнее время много чего по этому поводу проскочило, кто-то просит решение, кто-то консультацию и прочее-прочее....

Ты всего 6 сообщений на форум написал, а уже что-то успело проскочить... Впечатлительный ты, однако smile

Цитата(primax @ 26.11.2007, 19:26

)

Совет по той части которая у тебя пропущена (поиск для А и В одновременно, моя предложеная реализация выше):

А если хочется чего-то большего, чем просто перебор?

Автор: Akina 27.11.2007, 00:45

Цитата(KasMP @ 27.11.2007, 01:07

)

только в том случае, когда пользователь сможет увидеть разложение на множители (что и реализовано в указанной выше теме).

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

Цитата(KasMP @ 27.11.2007, 01:07

)

Взгляни(те), пожалуйста, вот на эту тему

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

Автор: KasMP 27.11.2007, 07:33