Каталог по источникам

Задачи

Страница: 1 2 3 4 5 6 7 >> [Всего задач: 78]

Задача 76209

Темы:	[	Знакомство с циклами	]
	[	Задачи с целыми числами	]
	[	НОД и НОК. Алгоритм Евклида	]

Сложность: 2-

Даны два натуральных числа a и b, не равные нулю одновременно. Вычислить НОД(a,b) — наибольший общий делитель а и b.

Решение

Вариант 1.

        if a > b then begin
        | k := a;
        end else begin
        | k := b;
        end;
        {k = max (a,b)}
        {инвариант: никакое  число, большее k, не является
          общим делителем}
        while not ((a mod k = 0) and (b mod k = 0)) do begin
        | k := k - 1;
        end;
        {k - общий делитель, большие - нет}

Вариант 2 (алгоритм Евклида). Будем считать, что НОД(0,0)=0. Тогда НОД(a,b) = НОД(a-b,b) = НОД(a,b-a); НОД(a,0) = НОД(0,a) = a для всех a,b≥0.

         m := a; n := b;
        {инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 }
        while not ((m=0) or (n=0)) do begin
        | if m >= n then begin
        | | m := m - n;
        | end else begin
        | | n := n - m;
        | end;
        end;
        {m = 0 или n = 0}
        if m = 0 then begin
        | k := n;
        end else begin {n = 0}
        | k := m;
        end;

Прислать комментарий

Задача 76210

Темы:	[	Знакомство с циклами	]
	[	Задачи с целыми числами	]
	[	НОД и НОК. Алгоритм Евклида	]

Сложность: 2-

Написать модифицированный вариант алгоритма Евклида, использующий соотношения НОД(a,b) = НОД(a mod b, b) при a≥b, НОД(a,b) = НОД(a, b mod a) при b≥a.

Прислать комментарий

Задача 76219

Темы:	[	Знакомство с циклами	]
	[	Условный оператор	]
	[	Задачи с целыми числами	]

Сложность: 2-

Составить программу решения предыдущей задачи, использующую тот факт, что составное число имеет делитель, не превосходящий квадратного корня из этого числа.

Решение

Во втором варианте решения вместо l:=l+1 можно написать

                if l*l > k then begin
                | l:=k;
                end else begin
                | l:=l+1;
                end;

Прислать комментарий

Задача 76240

Тема:

[

Многомерные массивы

]

Сложность: 2-

(Сообщил А. Л.Брудно) Прямоугольное поле m×n разбито на mn квадратных клеток. Некоторые клетки покрашены в чёрный цвет. Известно, что все чёрные клетки могут быть разбиты на несколько непересекающихся и не имеющих общих вершин чёрных прямоугольников. Считая, что цвета клеток даны в виде массива типа

array[1..m] of array [ 1..n] of boolean;

подсчитать число чёрных прямоугольников, о которых шла речь. Число действий должно быть порядка mn.

Решение

Число прямоугольников равно числу их левых верхних углов. Является ли клетка верхним углом, можно узнать, посмотрев на её цвет, а также цвет верхнего и левого соседей. (Не забудьте, что их может не быть, если клетка с краю.)

Прислать комментарий

Задача 76203

Тема:

[

Знакомство с циклами

]

Сложность: 2

Дано натуральное (целое неотрицательное) число а и целое положительное число d. Вычислить частное q и остаток r при делении а на d, не используя операций div и mod.

Решение

Согласно определению, a = q^.d + r, 0≤r < d.

        {a >= 0; d > 0}
        r := a; q := 0;
        {инвариант: a = q * d + r, 0 <= r}
        while not (r < d) do begin
        | {r >= d}
        | r := r - d; {r >= 0}
        | q := q + 1;
        end;

Прислать комментарий

Страница: 1 2 3 4 5 6 7 >> [Всего задач: 78]