Міністерство шляхів сполучення Російської Федерації
Далекосхідний державний університет
шляхів сполучення
Кафедра "Інформаційні технології та системи"
Курсова робота з інформатики
Варіант № 9
Виконав: ст.
419г. Кіршем І. Ф.
Перевірив:
Березне Д. П.
1998
Скласти програму визначення мінімального числа квітів, необхідних длярозмальовки карти довільної конфігурації таким чином, щоб країни зоднаковою розфарбуванням не стикалися. Схему меж карти представитимасивом. На зовнішніх файлах розташувати 3 - 4 схеми розташуваннякраїн. Підсумки представити у вигляді тексту із зазначенням обраних длякожної з країн квітів. Бажано завершити програму графічнимдодатком.
Змінні:
"num" - номер файла, що обирається користувачем.
"filen" - ім'я файлу.
" g [1 .. 100] - масив, який використовується "генератором перебору всіх варіантів"
"s: array [i, j]" - масив "зв'язків" показує, чи є зв'язок міжкраїнами "i" і "j".
"n" - кількість квітів, що використовуються для розмальовки.
"max - максимально можливу кількість країн (визначається призчитуванні даних).
"s1, s2, k, j, i, a" - змінні, для роботи "генератора".
"f, f1" - змінні для роботи з файлами.
"function get: integer;"
Функція зчитує поточне число, з файлу пов'язаного зі змінною -
"f" і шукає Максимальна кількість з усіх лічених.
Поки рядок =''або символ є:
- цифрою,
- "-",
- "." зчитує символ.
Якщо символ є:
- цифрою,
- "-",
- ".",то він додається в рядок "s".
Рядок цифр "s" перетворюється в число. Якщо "max" менше числа, то
"max" прирівнюється зовсiм небагато.
"function pr: boolean;"
Функція перевіряє, чи можна країну - i зафарбувати кольором - g [i]
(Чи можна заглиблюватися по дереву).
Перебирає все розфарбовані країни (від "1" до "i-1") і порівнює кольорукожній з них з кольором країни "i".
"function gen (n: integer): boolean;"
Функція, що визначає можливість розмальовки країн "n"-м кол-вомквітів.
Кожному елементу масиву "g" присвоює значення рівне "0". Поточномуномеру даної країни "i" задає значення "1".
Повторює дії:
Повторює дію:
До номером кольору даної країни додати "1" ( "g [i] : = g [i] 1; "),поки не можна країну "i" розфарбувати в колір "g [i]" або колір "i"-ї країни небільше числа "n". Якщо колір "i"-ї країни більше числа "n" то:
номером кольору розглянутої
країни прирівнює "0" і знижує номер даної країни на "1".
Інакше підвищує номер даної країни на "1", поки номерданої країни не дорівнює "1" або номер даної країни небільше кількості країн.
Значення функції одно "True", якщо номер даної країнибільше кількості країн.
Основна програма:
Висновок повідомлень користувачеві (див. робочу програму)
Запит номера файлу ( "num ").
Виконуються дії в змінну "num" запитується символ натиснутоюклавіші, якщо натиснута клавіша не від 1 до 3 то виводиться повідомлення про помилкупоки не натиснута клавіша від 1 до 3.
Формується ім'я вихідного файлу filen: = 'input' + num + '. txt'.
Повідомлення користувачеві про обраний файл.
Зчитування даних
Відкриється файл "filen" для зчитування даних.
"max: = 0".
Кожній комірці масиву зв'язків привласнюється "брехня"
Поки файл не скінчився зчитуються пара країн, в масив зв'язків зіндексами: [країна з меншим номером, з великим] присвоюється значенняістина.
Закривається файл "filen".
Блок, який визначає мінімальну кількість квітів.
Початкова кількість квітів = 1.
Повторювати дії:
Підвищити кількість квітів на одиницю.
Ще не можлива розфарбування всіх країн даними кількістю квітів.
Запис даних.
Створити файл "Output.txt". Рахувати в нього кількість квітів. Вважатив нього список розмальовки країн. Закрити файл.
Текст програми
program mag; uses crt; var num: char; filen: string; g: array [1 .. 100] of integer; s: array [ 1 .. 100,1 .. 100] of boolean; max, s1, s2, j, n, i, a: integer; f: file of char; f1: text;
(Функція зчитує поточне число, з файлу пов'язаного з пеpеменной - f. )
function get: integer; var k, c: integer; s: string; ch: char; begin s :=''; k: = 50; while ((s ='') or ( k = 43) or (k = 45) or ((k> 47) and (k47) and (k1 then for j: = 1 to i-1 do if s [j, i] then if g [i] = g [j] then pr: = false; end;
function gen (n: integer): boolean; begin for j: = 1 to max do g [j]: = 0; i: = 1; repeat repeat g [i]: = g [i] +1; until pr or (g [i]> n); if (g [i]> n) then begin g [i]: = 0; i: = i -1; end else i: = i +1; until (i = 1) or (i> max); gen: = i> max; end;begin clrscr; writeln ( 'Haжміте цифру, що вказує номер файла'); writeln ( 'з якого будуть счтиваться дані.'); writeln (''); for i: = 1 to 3 do writeln ( '', i, '-- файл input ', i,'. txt');
(Запpос номеp файлу.) repeat num: = readkey; if not ((num = '1 ') or (num = '2') or (num = '3 ')) then writeln (' Ви в чомусь помилилися '); until (num = '1') or (num = '2 ') or (num = '3'); filen: = ' input '+ num +'. txt '; writeln (''); writeln (' Обрано файл - ', filen); writeln ('');
(Зчитування даних)
Assign (f, filen); Reset (f); max: = 0; for s1: = 1 to 100 do for s2: = 1 to 100 do s [s1, s2]: = false; while not eof (f) do begin s1: = get; s2: = get; if s1> s2 then s [s2, s1]: = true else s [s1, s2]: = true; end;
Close (f);
n: = 1; repeat n: = n +1; until gen (n);
(Виведення даних у файл - 'output.txt'.}
Assign (f1, 'output.txt'); Rewrite (f1); writeln (f1, 'Число країн =', max); writeln (f1 ,''); writeln (f1, 'N Cтрана =', n); for j: = 1 to max do writeln (f1, 'КРАЇНИ -', j, ', колір -', g [j], '');
Close (f1); end .
Koнец.
Дані з Input1.txt:
1 2 1 7 2 7 2 3 2 8 3 4 3 9 3 8 4 9 4 5 5 6 5 9 5 13
6 13 6 14 6 15 7 8 7 11 8 9 8 10 8 11 9 10 9 12 9 13
10 11 10 12 10 14 11 15 12 14 13 14 14 15
Результат в output.txt:
Кількість країн = 15
N країн = 4 країна - 1, колір - 1 країна -- 2, колір - країна 2 - 3, колір - 1 країна - 4, колір - 2 країна - 5, колір - 1 країна - 6, колір - 2 країна - 7, колір - 3 країна - 8, колір - 4 країна - 9 , колір - 3 країна - 10, колір - 1 країна - 11, колір - 2 країна - 12, колір - 2 країна - 13, колір - 4 країна - 14, колір - 3 країна - 15, колір - 1
