Методика решения зада по теме «Программирование».

Дата: 2025-06-02; Просмотры: 9

Оценка:

0.00 из 5.00 — оценок

Скачиваний: 0

Пример 1: имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.

Входные данные:

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

Пример организации исходных данных во входном файле:

1 3

5 12

6 9

5 4

3 3

1 1

Для указанных входных данных значением искомой суммы должно быть число 32.

В ответе укажите два числа: сначала значение искомой суммы для файла А(рис.), затем для файла B(рис.).

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

Рисунок – Фрагменты файлов A (слева) и B (справа)

Решение: начальное значение суммы S=0, учесть очередной элемент Y – просто прибавить его к текущей сумме. Если перейти к рассмотрению пар, то очередной суммируемый элемент – это наибольшее из чисел пары. С учетом этого, можно записать такой алгоритм:

Подсчитали максимально возможную сумму, выбрав по одному элементу из пары. Но есть дополнительное условие – сумма S не должна делится на 3. Поэтому перед выводом S нужно проверить это условие. Если S кратно 3, то решение должно быть другое. Очевидно, другое решение получится, если одно из выбранных чисел заменить на другое число из той же пары, но имеющее другой остаток при делении на 3. А чтобы сумма была максимальной, нужно среди всех пар отобрать те, где «напарники» имеют разный остаток при делении на 3. А среди этих пар найти максимальное число, не входящее в сумму. При замене числа на его напарника, сумма S уменьшится. Можно для каждой пары (X1, X2) определить разность D=|X1-X2| и среди всех разностей найти минимальную Dmin. Тогда при уменьшении S на эту минимальную разность, S будет максимальная из возможных.

Имеют ли элементы разные остатки при делении на 3 тоже можно учитывать по этой разности D (если она кратна 3, то ее не учитываем, т.к. она не способна обеспечить условие «S не делится на 3»).

При поиске минимума, начальное значение минимума должно быть максимально (или больше максимально возможного). Поскольку каждое число в паре от 1 до 10000, то можно взять начальное 10000 (а можно 9999).

АЛГ Сумма последовательности пар

| Сумма не кратна 3

НАЧАЛО

S:=0;

Dmin:=10000; |начальное значение минимума должно быть максимально

ЦИКЛ по всем парам

НЦ

X1,X2 – очередная пара элементов

|прибавляем к сумме наибольший из пары

ЕСЛИ X1>X2 ТО

S:=S+X1

D:=X1-X2; |разность элементов

ИНАЧЕ

S:=S+X2

D:=X2-X1; |разность элементов

ВСЕ

| разность учитываем, только если она

| не кратна 3

ЕСЛИ D не кратно 3 ТО

|возможно, это новый минимум

ЕСЛИ D < Dmin ТО

Dmin:=D |коррекция минимума

ВСЕ

КЦ

| проверим S, при необходимости изменим

ЕСЛИ S кратно 3 ТО

S:=S-Dmin

ВСЕ

ВЫВОД S

КОНЕЦ

Хапишем программу на языке Паскаль:

CONST

Xmax=10000; {максимальное значение чисел в паре}

{name='А.txt';}

name='В.txt';

VAR

f:text;

S:integer; {значение суммы}

X1,X2: integer; {текущая пара}

D, Dmin : integer; {текущая и минимальная разность элементов пары}

N:integer; {число пар в файле}

i: integer; {счетчик пар}

BEGIN

assign(f,name); {присвоить файлу f имя name}

reset(f); {открыть файл для чтения}

S:=0; {начальное значение для суммы}

Dmin:=Xmax; {начальное значение минимума}

readln(f,N);{прочитать число пар из файла}

{перебираем все пары с 1-й по N-ю}

for i:=1 to N do begin

readln(f,X1,X2); {считываем очередную пару из файла}

if X1>X2 then begin

S:=S+X1;

D:=X1-X2;

end

else begin

S:=S+X2;

D:=X2-X1;

end;

{учитываем только разности не кратные 3}

if D mod 3 <>0 then begin

{возможная коррекция минимума}

if D<Dmin then Dmin:=D;

end;

close(f);{закрыть файл}

{S=максимальная сумма, Dmin -корректировка, если S не подойдет}

if S mod 3 = 0 then {требуется корректировка}

S:=S-Dmin; {корректируем}

writeln(S); {вывод результата}

END.

Можно изменять имя файла в константе name. Для файла А.txt получим ответ равный 127127. Для файла В.txt ответ будет 399762080.

Пример 2: Последовательность натуральных чисел характеризуется числом Х — наибольшим числом, кратным 14 и являющимся произведением двух элементов последовательности с различными номерами. Гарантируется, что хотя бы одно такое произведение в последовательности есть. (файл а2 и b2)

Входные данные.

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

Пример организации исходных данных во входном файле:

1000

Пример выходных данных для приведённого выше примера входных данных: 28000

В ответе укажите два числа: сначала значение искомого произведения для файла А (рис.), затем для файла B (рис.).

Рисунок – Фрагменты файлов A (слева) и B (справа)

Решение: чтобы произведение было максимальным, его множители должны быть максимальны.

Получить произведение кратное 14 можно двумя способами:

1) один из множителей делится на 2 (Max2), другой на 7 (Max7);

2) один из множителей делится на 14 (Max14), другой – любое число (Max).

Но кроме того, требуется чтобы перемножались числа последовательности с разными номерами. Для этого в первом случае будем перемножать максимальное четное число не кратное 7 и максимальное нечетное число кратное 7, тогда числа будут различны, а значит, иметь и разные номера.

Во втором случае, можно использовать схему поиска максимума (сравнение очередного числа с текущим максимумом). Но если число стало новым максимумом среди кратных 14, то не пытаемся его проверить на максимум среди произвольных чисел. Если в последовательности два максимальных числа кратных 14, то первое из них станет Max14, а другое, поскольку не приводит к смене Max14, станет новым максимумом Max.

Но если в последовательности два наибольших числа кратны 14, то, при таком поиске, большее из них будет Max14, а меньшее не попадет в Max. Поэтому необходимо при смене Max14 предыдущее значение максимума использовать для корректировки Max.

После поиска этих максимумов осталось сравнить произведения

Max2*Max7 и Max14*Max. Число Х равно наибольшему их них.

НАЧАЛО

| начальные значения максимумов берем наименьшими

Мах2:=0;

Мах7:=0;

Мах14:=0;

Мах:=0;

ЦИКЛ по всем числам

НЦ

d:= очередное число

| поиск максимума среди четных чисел некратных 7

ЕСЛИ d четно И d не кратно 7 И d > Max2 ТО Max2:=d ВСЕ

| поиск максимума среди нечетных чисел кратных 7

ЕСЛИ d нечетно И d кратно 7 И d > Max7 ТО Max7:=d ВСЕ

| если это новый максимум для Max14

ЕСЛИ d кратно 14 И d > Max14 ТО

| возможно старый максимум подойдет для Max

ЕСЛИ Max14 > Max ТО Max := Max14 ВСЕ

Max14 := d; | новый максимум для кратных 14

ИНАЧЕ |для Max14 не подошел, возможно подойдет для Max

ЕСЛИ d > Max ТО Max := d; ВСЕ

КЦ

| найдены Max2, Max7, Max14 и Max

|выбираем Х как максимум из двух произведений}

ЕСЛИ Max7*Max2 > Max14*Max ТО

X:=Max7*Max2

ИНАЧЕ

X:=Max14*Max;

ВСЕ

ВЫВОД Х | вывод результата

КОНЕЦ

Напишем программу на языке Паскаль:

CONST

{имя файла с входными данными}

{name='А.txt';}

name='В.txt';

VAR

f:text;{файл с данными}

N:integer; {кол-во чисел в файле}

i: integer; {счетчик чисел}

Max2, {максимальное четное число не кратное 7}

Max7, {максимальное нечетное число кратное 7}

Max14, {максимальное число кратное 14}

Max, {максимальное из всех чисел, отличное по номеру от Max14}

d : integer; {очередное число}

X: integer; {число-результат}

BEGIN

assign(f,name); {присвоить файлу f имя name}

reset(f); {открыть файл для чтения}

{начальные значения максимумов}

Max2:=0;

Max7:=0;

Max14:=0;

Max:=0;

readln(f,N);{прочитать кол-во чисел из файла}

{перебираем все числа}

for i:=1 to N do begin

readln(f,d); {считываем очередное число из файла}

{поиск максимума среди четных чисел некратных 7}

if (d mod 2 = 0) and (d mod 7 > 0) and (d > Max2) then Max2:=d;

{поиск максимума среди нечетных чисел кратных 7}

if (d mod 7 = 0) and (d mod 2 > 0) and (d > Max7) then Max7:=d;

{если это новый максимум для Max14 }

if (d mod 14 = 0) and (d > Max14) then begin

{возможно старый максимум подойдет для Max}

if Max14 > Max then Max := Max14;

Max14 := d;

end

else {для Max14 не подошел, возможно подойдет для Max}

if d > Max then Max := d;

end;

{найдены Max2, Max7, Max14 и Max}

{выбираем Х как максимум из двух произведений}

if (Max7*Max2 > Max14*Max) then

X:=Max7*Max2

else

X:=Max14*Max;

writeln(X); {вывод результата}

END.

Для файла A.txt программа выдает результат 447552

Для файла В.txt программа выдает результат 994000

Пример 3: набор данных состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел в первой группе должна быть чётной, во второй — нечётной. Определите минимально возможную сумму всех чисел в третьей группе.

Входные данные. (файл А и В)

Первая строка входного файла содержит число N — общее количество троек в наборе. Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.

Пример входного файла:

1 2 3

8 12 4

6 9 7

Для указанных данных искомая сумма равна 11, она соответствует такому распределению чисел по группам: (2, 8, 7), (3, 12, 9), (1, 4, 6).

Вам даны два входных файла A (рис.) и B(рис.), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

Рисунок – Фрагменты файлов A (слева) и B (справа)

Решение: чтобы сумма чисел была минимальной, нужно в каждой тройке выбирать минимальное число. Но можно ли из остальных двух чисел составить суммы разной четности? Будем из каждой тройки выбирать минимальное число и считать сумму этих минимумов (S). Из остальных двух чисел тройки будем одно из чисел прибавлять к одной сумме S1, другое – к другой сумме S2 (какое именно из двух чисел к какой сумме – неважно). Если в результате S1 и S2 получились разной четности, то задача решена. В этом случае S1 или S2 – сумма чисел первой или второй группы, а минимальная сумма 3-й группы равна S.

Если S1 и S2 имеют одинаковую четность, то это нельзя исправить перестановкой двух чисел, оставшихся после выбора минимума. Ведь если два этих числа имеют одинаковую четность, то четность S1 и S2 не изменится в результате перестановки чисел. А если четность этих двух чисел разная, то S1 и S2 одновременно изменят четность и опять станут одинаковой четности.

Поэтому сделать S1 и S2 разной четности можно только выбрав другой минимум в какой-то тройке. Причем это новое число должно быть: во-первых, другой четности; во-вторых, разница между новым и старым числом должна быть минимальна.

Для этого необходимо в каждой тройке вычислять разницу между минимальным числом тройки и остальными двумя числами этой тройки. Среди всех этих разностей всех троек нужно отобрать нечетные, а среди всех нечетных разностей найти минимум Dmin.

Имея минимальную сумму S и минимальную нечетную разность Dmin, можно выдать ответ: если S1 и S2 разной четности, то ответ S, если одинаковой, то S+Dmin.

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

Алгоритм:

АЛГ Минимум суммы

НАЧАЛО

S:=0; S1:=0; S2:=0; | начальное значение сумм

Dmin:= Xmax; |начальное значение минимума должно быть максимально

ЦИКЛ по всем тройкам

НЦ

x,y,z – очередная тройка элементов

|переставляем элементы, чтобы x=min(x,y,z)

ЕСЛИ x>y ТО переставить х,y ВСЕ

ЕСЛИ x>z ТО переставить х,z ВСЕ

| теперь x=min(x,y,z)

S:=S+x; |считаем сумму минимальных элементов

S1:=S1+y;|считаем первую сумму

S2:=S2+z;|считаем вторую сумму

D:=y-x; |текущая разность элементов

|если разность четна или не минимальна в этой тройке }

ЕСЛИ D четно ИЛИ D > z-x ТО

D:=z-x; |использовать разность другого элемента

ВСЕ

| если разность нечетна, то пробуем корректировать минимум

ЕСЛИ D нечетно И D<Dmin ТО Dmin:=D ВСЕ

КЦ

ЕСЛИ S1 и S2 одной четности ТО

|одинаковая четность, требуется корpектировка

ЕСЛИ Dmin=Xmax ТО |замену другой четности не нашли

S:=0 |0-знак того,что решений нет

ИНАЧЕ

S:=S+Dmin; |корректируем сумму

ВСЕ

ВЫВОД S

КОНЕЦ

Напишем программу на языке Паскаль.

CONST

Xmax=10000; {маскимальное значение чисел в паре}

{имя файла с входными данными}

{name='a3.txt'; }

name='a3.txt';

VAR

f:text;

S:integer; {значение 3-й суммы}

S1,S2 : integer;

x,y,z: integer; {текущая тройка}

D, Dmin : integer; {текущая и минимальная разность элементов тройки}

N:integer; {число троек в файле}

i: integer; {счетчик троек}

BEGIN

assign(f,name); {присвоить файлу f имя name}

reset(f); {открыть файл для чтения}

{начально значение для сумм}

S:=0; S1:=0; S2:=0;

Dmin:=Xmax; {за начальное значение минимума берем максимально возможное}

readln(f,N);{прочитать число троек из файла}

{перебираем все тройки с 1-й по N-ю}

for i:=1 to N do begin

readln(f,x,y, z); {считываем очередную тройку из файла}

if x>y then begin {переставим x,y}

D:=x;

x:=y;

y:=D;

end;

{x=min(x,y)}

if x>z then begin {переставим x,z}

D:=x;

x:=z;

z:=D;

end; {x=min(x,y,z)}

S:=S+x;{считаем сумму минимальных элементов}

S1:=S1+y;{считаем первую сумму}

S2:=S2+z;{считаем вторую сумму}

D:=y-x; {разность элементов}

{если разность четна или не минимальна в этой тройке }

if (D mod 2 =0) or (D > z-x) then

D:=z-x; {использовать разность другого элемента }

{если разность нечетна, то пробуем корректировать минимум}

if (D mod 2 >0) and (D<Dmin) then

Dmin:=D;

end;

close(f);{закрыть файл}

{S=минимальная сумма,Dmin -корректировка,если S не подойдет}

if S1 mod 2 = S2 mod 2 then {одинаковая четность, требуется коректировка}

if (Dmin=Xmax) then {замену другой четности не нашли}

S:=0 {0-знак того,что решений нет}

else

S:=S+Dmin; {корректируем сумму}

writeln(S); {вывод результата}

END.

Для файла А.txt ответ будет 185

Для файла В.txt ответ будет 100918194