Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Министерство путей сообщения Российской Федерации
Дальневосточный государственный университет
путей сообщения
Кафедра ”Информационные технологии и системы ”
Выполнил: ст. 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" приравнивается считанному числу.
"function pr:boolean;"
Функция проверяет, можно ли страну - i закрасить цветом - g[i] (Можно ли углубляться по дереву).
Перебирает все раскрашенные страны (от "1" до "i-1") и сравнивает цвета каждой из них с цветом страны "i".
"function gen(n:integer):boolean;"
Функция, определяющая возможность раскраски стран "n"-ым кол-вом цветов.
Каждому элементу массива "g" присваивает значение равное "0". Текущему номеру рассматриваемой страны "i" задает значение "1".
Повторяет действия:
Повторяет действие:
страны приравнивает "0" и
понижает номер рассматриваемой страны на "1".
Иначе повышает номер рассматриваемой страны на "1", пока номер рассматриваемой страны не равен "1" или номер рассматриваемой страны не больше количества стран.
Основная программа:
Выполняются действия в переменную "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(k<58)))and(not eof(f)) do
begin
read(f,ch); k:=ord(ch);
if (k=43)or(k=45)or((k>47)and(k<58)) then s:=s+ch;
end;
val(s,c,k);
if max< c then max:=c;
get:=c;
end;
{ Функция проверяет, можно ли страну - i
закрасить цветом - g[i]. }
function pr:boolean;
var j:integer;
begin
pr:=true;
if i>1 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,'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