Задача 219. 219. Скласти програму для розв’язання системи n лінійних рівнянь з n невідомими.
Розв’язання: Задача цікава тим, що вона досить часто постає при розв’язанні фізичних, технічних, економічних та інших практичних задач. У загальному вигляді система n лінійних рівнянь з n невідомими записується у вигляді:
Двомірний масив, або матриця, утворена з коефіцієнтів біля невідомих, називається матрицею коефіцієнтів даної системи, а одномірний масив, утворений з правих частин рівняння називається порядком системи. Найбільш поширеним алгоритмом розв’язання систем лінійних рівнянь є алгоритм Гауса, або як його інколи називають – алгоритм виключення невідомих. Пояснимо дію алгоритму на конкретному прикладі, а потім напишемо програму для загального випадку.
Нехай у нас є система трьох рівнянь з трьома невідомими, або іншими словами – дано систему лінійних рівнянь третього порядку.
Хід розв’язання методом виключення невідомих вам добре відомий з курсу математики, томи ми його просто покажемо. Якщо ж у когось виникнуть труднощі з розумінням ходу розв’язання, то ми в черговий раз рекомендуємо відкласти в сторону на деякий час даний підручник і засісти за підручник математики.
Остання система легко розв’язується поступовою підстановкою значень змінних від останнього рівняння до першого: х3 = 4, х2 = –2, х1 = 3.
Весь хід нашого розв’язання можна умовно розбити на дві частини: зведення системи 3-го порядку до рівносильної їй трикутної системи з одиничними коефіцієнтами по діагоналі (цей етап називається прямим ходом алгоритму Гауса), а потім обчислення невідомих, починаючи з кінця (зворотній хід). Зауважимо, що розв’язання даним методом можливе лише тоді, коли початкова система сумісна і має єдиний розв’язок.
При програмній реалізації даного алгоритму необхідно врахувати декілька моментів, а саме: на деякому етапі черговий коефіцієнт, що нам потрібно знайти, може бути рівним нулю. Або ж при діленні, яке ми виконуємо постійно, можемо отримати число, яке може виявитись настільки малим, що для нашого електронного друга воно в пам’яті відображатиметься нулем. Для того, щоб обійти ці невеликі підводні рифи удосконалимо розв’язання у загальному випадку таким чином, що на кожному черговому етапі будемо виключати невідоме з найбільшим за модулем коефіцієнтом, іншими словами, ми будемо переставляти рядки матриці (міняти місцями рівняння).
Ми приведемо кінцеву програму алгоритму Гауса з відповідними коментарями у потрібних місцях. Надіємось, що ви вже досягли того рівня класності у програмуванні, коли найбільш прості алгоритми, що використовуються у програмі, вам зрозумілі прямо з тексту програми.
program Gaus;
uses dos, crt;
const k = 20;
type urawnenie = array[1..k+1] of real;
matrix = array[1..k] of urawnenie;
bar = array[1..k] of real;
var mas: matrix;
x: bar;
max, f: real;
i, j, n, d, l: integer;
begin
{ Введення вхiдних даних }
write('Введiть порядок системи: ');readln(n);
for i:= 1 to n do
begin
for j:= 1 to n do
begin
write('a[',i,',',j,'] = ');
readln(mas[i][j]);
end;
write('b[',i,'] = ');
readln(mas[i][n+1]);
end;
{ Виведення iх на екран у звичному виглядi }
writeln('Програма розв''язуе методом Гауса систему: ');
for i:= 1 to n do
begin
for j:= 1 to n+1 do
if j < n+1 then
if j = 1 then write(mas[i][j]:2:1,' x',j)
else if mas[i][j] < 0 then write(' - ',-mas[i][j]:2:1,' x',j)
else write(' + ',mas[i][j]:2:1,' x',j)
else write(' = ',mas[i][j]:2:1);
writeln;
end;
{ Алгоритм Гауса - прямий хiд }
for i:= 1 to n do
begin
{ вибiр рiвняння з найбiльшим за модулем коеф. при х[i] }
max:= abs(mas[i][i]);
d:= i;
for l:= i+1 to n do
if abs(mas[l][i]) > max then
begin
max:= abs(mas[l][i]);
d:= l;
end;
{ якщо потрiбно, то переставили мicцями два рiвняння }
if d <> i then
for j:= i to n+1 do
begin
f:= mas[i][j];
mas[i][j]:= mas[d][j];
mas[d][j]:= f;
end;
{ дiлимо i-те рiвняння на коеф. при x[i] }
f:= mas[i][i];
for j:= i+1 to n+1 do mas[i][j]:= mas[i][j]/f;
{ виключаемо x[i] з усiх рiвняннь, що стоять нижче }
for l:= i+1 to n do
begin
{ виключаемо x[i] з l-го рiвняння }
f:= mas[l][i];
for j:= i+1 to n+1 do mas[l][j]:= mas[l][j] - mas[i][j]*f;
end;
end;
{ кiнець прямого ходу i початок зворотнього }
x[n]:= mas[n][n+1];
for i:= n-1 downto 1 do
begin
x[i]:= mas[i][n+1];
for j:= i+1 to n do x[i]:= x[i] - mas[i][j]*x[j]
end;
{ виведення результатiв }
writeln; writeln('Коренi системи рiвнянь:');
for i:=1 to n do write(' x[',i,'] = ',x[i]:2:1);
readln;
end.
Задача 220. 220. ( завдання олімпіади Київського фізмат ліцею у 1998-99 навчальному році )
“Гроші на шахівниці”
На кожній клітинці шахівниці розміром Mx N клітин випадковим чином розкладено монети, загальна вартість яких не перевищує 3333$. Пішак можу рухатись або праворуч, або вгору (на одне поле за один хід) від нижнього лівого поля до правого. З усіх клітин, на яких побував пішак знімають монети і складають у сейф.
Завдання. Створіть програму MONEY.*, яка допоможе таким чином зібрати найбільшу кількість монет
Вхідні дані. Перший рядок вхідного файлу MONEY.DAT містить у вказаному порядку натуральні числа M i N, менші за 22. Для j в межах від 1 до M включно (j+1)-й рядок цього ж файлу містить сукупні вартості монет у клітинах j–го рядка шахівниці, якщо рахувати рядки згори до низу, у тому ж порядку, як вони (клітини цього рядка) розташовані на шахівниці. Наприклад:
2 3
1 2 3
6 8 2
Вихідні дані. Перший рядок вихідного файлу MONEY.RES має містити найбільшу кількість монет, яку можна зібрати таким чином. Наступний рядок цього ж файлу містить M+N–2 символи, що описують напрям ходів пішака (від першого до останнього): U – вгору (від англійського Up), R – праворуч (від англійського Right), які дають можливість зібрати найбільше грошей, і в якій хід праворуч здійснюється якомога пізніше на кожній ділянці шляху. Наприклад, для наведеного прикладу:
RUR
Розв’язання: Задачу можна розв’язувати різними способами. Ми познайомимо вас на прикладі даної задачі з однією з модифікацій “жадібного” алгоритму, який покладено в основу одного з методів динамічного програмування і який у даному випадку працює просто прекрасно і дає можливість знайти розв’язок всього за два проходження по масиву. Для більшої наочності візьмемо конкретний приклад. Нехай наша шахівниця має розмір 4 на 5. Розміщення монет на шахівниці відобразимо відповідною матрицею (Рис. 1).
| Рис. 1 | ||||||
| Рис. 2 | ||||||||
| Рис.3 | |||||||
| Рис. 4 | ||||||
На підставі даної матриці сформуємо нову, користуючись правилами ходу, описаними в умові задачі. Але у клітини нової матриці ми будемо заносити сумарні (вже зібрані) найбільші кількості монет. Зрозуміло, що в любу клітину нижнього рядка ми можемо попасти тільки з клітини розміщеної ліворуч, а в довільну клітину лівого стовпчика тільки з нижньої клітини, тому нова матриця після заповнення нижнього рядка і лівого стовпчика набуде вигляду, як показано на рисунку 2. У клітинку [3,2] ми можемо попасти або з клітинки [3,1], або з клітинки [4,2]. Зрозуміло, що нам вигідніше попасти в неї з клітинки розміщеної ліворуч ([3,1]), так як у цьому випадку ми зберемо більшу кількість монет. Аналогічні міркування застосуємо до всіх клітинок незаповненого нижнього рядка, рухаючись зліва направо і вибираючи ту з двох клітин, розміщених ліворуч або нижче, прийшовши з якої ми зберемо більшу кількість монет. Такі алгоритми, що грунтуються завжди на виборі більшого з можливих варіантів прийнято називати «жадібними». Застосувавши описаний алгоритм до конкретного прикладу, отримаємо масив для сумарної кількості монет, зображений на рис. 3. Після заповнення всього масиву здійснюємо зворотний хід по новоутвореному масиву рухаючись або вліво, або вниз, вибираючи ту з комірок, у якій міститься більша кількість монет. При рівній кількості монет у вказаних комірках ми будемо вибирати комірку, що знаходиться ліворуч, так як згідно умови задачі ми повинні рухатись праворуч як можна пізніше. Оскільки рухаючись назад ми ліворуч підемо раніше, то при прямому ході ми праворуч звернемо пізніше. Маршрут, отриманий таким чином, відображено жирним шрифтом на рисунку 4. Нам залишилось привести програму, що повністю реалізує описаний алгоритм і розв’язує поставлену задачу. Необхідні пояснення приведено в коментарях до програми. Одразу наголосимо, що для наочності ми будемо у програмі виводити обидва масиви і маршрут руху на екран. Модифікувати програму для випадку виводу у файл, як того вимагає умова задачі ми надаємо право вам.
program money;
var m, n, i, j: integer;
mon, res: array[1..21,1..21] of integer;
f: text; st: string;
begin
st:= '';
assign(f,'money.dat'); reset(f); { згадайте роботу з файлами – див. §2.5 }
readln(f,m,n); { зчитали розміри шахівниці }
for j:=1 to m do
for i:=1 to n do
begin
read(f,mon[j,i]); { зчитуємо дані про розміщення монет }
end;
close(f);{ закрили файл }
{ Зверніть увагу на наступний рядок! Виявляється у Паскалі з цілими маси вами можна працювати як з окремими змінними. }
res:=mon; { однією командою скопіювали весь масив! }
for j:=1 to m do
begin
for i:=1 to n do write(mon[j,i]:5); { вивели масив на екран }
writeln;
end;
writeln;
{ утворюємо новий масив – спочатку заповнюємо лівий стовпчик }
for j:=m-1 downto 1 do res[j,1]:=res[j,1]+res[j+1,1];
{ а потім нижній рядок }
for i:=2 to n do res[m,i]:=res[m,i]+res[m,i-1];
{ після цього реалізуємо алгоритм заповнення тієї частини нового масиву, що залишилась – вибираємо більшу з лівої або нижньої кількості монет – «жадібний» алгоритм }
for j:=m-1 downto 1 do
for i:=2 to n do
if res[j+1,i]>res[j,i-1] then res[j,i]:=res[j,i]+res[j+1,i]
else res[j,i]:=res[j,i]+res[j,i-1];
{ виводимо новоутворений масив на екран, знову ж таки тільки з метою кращої наочності }
for j:=1 to m do
begin
for i:=1 to n do write(res[j,i]:5);
writeln;
end;
writeln(res[1,n]); { вивели найбільшу кількість монет }
{ і реалізуємо зворотний хід згідно описаного алгоритму }
j:=1; i:=n;
repeat
if j<m then
begin
if res[j+1,i] > res[j,i-1] then { причому, якщо потрібно йти вниз }
begin
j:=j+1; st:=st+'u'; { то пишемо що потрібно йти вгору }
end
else if i>1 then
if res[j,i-1] >= res[j+1,i] then { а якщо вліво }
begin
i:=i-1; st:=st+'r'; { то пишемо, що вправо }
end;
end;
{ якщо дійшли до низу, то рухаємось тільки вліво }
if j=m then while i<>1 do begin
st:=st+'r';i:=i-1;
end;
{ а якщо дійшли до лівого краю, то рухаємось тільки вниз }
if i=1 then while j<>m do begin
st:=st+'u';j:=j+1;
end;
until (j=m) and (i=1);
{ оскільки ми здійснювали зворотний хід, то утворений маршрут потрібно вивести на екран у зворотному порядку: }
for i:=length(st) downto 1 do write(st[i]);
writeln;
readln
end.
