Модераторы: Poseidon

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Алгоритм] I=A*K+B*L, даны A, B, N; вывести I<=N 
V
    Опции темы
KasMP
Дата 17.11.2007, 19:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Здравствуйте, товарищи программисты! 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 
PM MAIL   Вверх
KasMP
Дата 17.11.2007, 19:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Здравствуйте, товарищи программисты! 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:30
PM MAIL   Вверх
esperant0
Дата 17.11.2007, 19:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 1
Всего: 14
Раздел по алгоритмам. А у вас вопрос по анализу кода? 

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


--------------------
 
 Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer 

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором  а затем стерто и которое он - пользователь не мог видеть. 
PM MAIL   Вверх
KasMP
Дата 17.11.2007, 19:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
esperant0, возможно, моя низкая квалификация дала о себе знать... Не судите строго студента.
Но вообще я имела в виду, что не могу составить часть алгоритма. В коде это место записано так:
Цитата
begin
{Не знаю, как сделать оптимально. Помогите, пожалуйста!}
end

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

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

Это сообщение отредактировал(а) KasMP - 17.11.2007, 20:01
PM MAIL   Вверх
primax
Дата 18.11.2007, 20:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 8
Регистрация: 29.12.2006
Где: НТУУ-КПИ.Киев

Репутация: нет
Всего: нет
Я не совсем понимаю условие задачи. 
Зачем искать 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.
PM WWW ICQ Skype   Вверх
KasMP
Дата 24.11.2007, 00:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(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 просто неотрицательные (т.е. могут равняться нулю...).
PM MAIL   Вверх
KasMP
Дата 24.11.2007, 01:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Пожалуйста, посмотрите на плод моих трудов, суть которого сводится к следующему:
  • по условию 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 

Это сообщение отредактировал(а) KasMP - 24.11.2007, 01:21
PM MAIL   Вверх
GIK
Дата 24.11.2007, 12:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Добрый человек
**


Профиль
Группа: Участник
Сообщений: 985
Регистрация: 3.6.2005
Где: я только не небыв ал

Репутация: 4
Всего: 14
Цитата

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

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

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



--------------------
Математика=>пиво=> програмирование, три вещи последовательны и совместимы !!!
Программирование - это не деятельнось! Программирование - это состояние души!
Бог - самый крутой программист.
PM MAIL ICQ   Вверх
mr.Anderson
Дата 24.11.2007, 15:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


iOS Lead Developer
****


Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: 16
Всего: 128
Цитата
Вобщем то понятно, но пониманий складывается уж очень много... Где предел числе? и у 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 соответственно.
Отсюда и пляшем с алгоритмом. Если не получится, я постараюсь помочь.

Это сообщение отредактировал(а) mr.Anderson - 24.11.2007, 15:53


--------------------
user posted image

user posted image
PM MAIL ICQ Skype   Вверх
GIK
Дата 24.11.2007, 16:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Добрый человек
**


Профиль
Группа: Участник
Сообщений: 985
Регистрация: 3.6.2005
Где: я только не небыв ал

Репутация: 4
Всего: 14
Спасибо конечно, но пропуская через цикл эти занчения, явно какой-то предел (100 или 100 000 например) должен существовать smile До какого числа диапазоны выстраивать? 


--------------------
Математика=>пиво=> програмирование, три вещи последовательны и совместимы !!!
Программирование - это не деятельнось! Программирование - это состояние души!
Бог - самый крутой программист.
PM MAIL ICQ   Вверх
mr.Anderson
Дата 24.11.2007, 18:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


iOS Lead Developer
****


Профиль
Группа: Участник Клуба
Сообщений: 3374
Регистрация: 20.12.2004
Где: далеко

Репутация: 16
Всего: 128
Дык. А я о чем речь вел? Вот алг (не проверял, правда...):
Код

...
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!' );



--------------------
user posted image

user posted image
PM MAIL ICQ Skype   Вверх
primax
Дата 25.11.2007, 02:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 8
Регистрация: 29.12.2006
Где: НТУУ-КПИ.Киев

Репутация: нет
Всего: нет
Цитата(KasMP @  24.11.2007,  00:40 Найти цитируемый пост)
Бесспорно, это так smile . Только по условию K и L просто неотрицательные (т.е. могут равняться нулю...). 

Не заметил этого в условии изложеным тобой  smile 
Цитата(KasMP @  24.11.2007,  00:40 Найти цитируемый пост)
Чтобы использовать функции... (задание по этой теме)

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

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

П.С. Кстати, там можно в 2 раза уменьшить сложно алгоритма (я про свой), если заметить что там после определеного момента идут симметричные результаты (вроде было так, не помню, неделю назад это заметил).  smile 
PM WWW ICQ Skype   Вверх
KasMP
Дата 26.11.2007, 16:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(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 
(неужели я вообще ничего не понимаю? smile )
Цитата(mr.Anderson @  24.11.2007,  15:48 Найти цитируемый пост)
Если не получится, я постараюсь помочь.
 Будьте добры!! smile  smile 
Цитата(GIK @  24.11.2007,  16:16 Найти цитируемый пост)
До какого числа диапазоны выстраивать?  
 Думаю, навряд ли имеет смысл брать слишком большие числа: проверить будет сложно. Имхо преподаватель, отвечая на мой вопрос, ограничится числом 100 (а на практике, скорее всего, не поднимется выше 50-60...).

Вобщем, предел(A)=предел(B)=предел(N)=100 smile .
Цитата(mr.Anderson @  24.11.2007, 18:32 Найти цитируемый пост)
Дык. А я о чем речь вел? Вот алг (не проверял, правда...):
 Мне не удалось проникнуться его сутью. К чему все это?


Вновь благодарю за прочтение моего полуламерского опуса.  smile  smile 
PM MAIL   Вверх
KasMP
Дата 26.11.2007, 17:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(primax @  25.11.2007,  02:47 Найти цитируемый пост)
Не заметил этого в условии изложеным тобой 
"... где K и L - целые неотрицательные числа."
Цитата(primax @  25.11.2007,  02:47 Найти цитируемый пост)
Хм. Задание реализовать программу используя подпрограммы (функции в даном случае)? или задание в том чтобы реализовать функции раздельного поиска (ну т.е. то что ты делала smile )?
Первое.
Цитата(primax @  25.11.2007,  02:47 Найти цитируемый пост)
В принципе могу завтра, если будет время, твою задачку доделать используя твою логику (т.е. твою задумку для достижения результата). 
Нет, это моя задачка, она МОЯ, я хочу сама, не надо делать за меня, я просто прошу совет!!!!!!!
PM MAIL   Вверх
Akina
Дата 26.11.2007, 18:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 17
Всего: 454
ну и чего? берем и считаем:

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.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.
PM MAIL WWW ICQ Jabber   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1031 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.