Курсовая по информатике
Министерство путей сообщения Российской Федерации
Дальневосточный государственный университет
путей сообщения
Кафедра ”Информационные технологии и системы ”
Курсовая работа по информатике
Вариант № 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;"
Пока строка = '' или символ является:
- цифрой,
- "-",
- "." считывает символ.
Если символ является:
- цифрой,
- "-",
- ".",
то он добавляется в строку "s".
Строка цифр "s" преобразуется в число. Если "max" меньше числа, то
"max" приравнивается считанному числу.
"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" или номер рассматриваемой страны не
больше количества стран.
Основная программа:
Вывод сообщений пользователю (см. рабочую программу)
Запрос номера файла ("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 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,'cтрана - ',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