Министерство образования и науки РФ. Курсовая работа 30 вариант Иванилова Т. Н. дата оценка роспись
 Скачать 20.13 Kb.
|
|
Министерство образования и науки РФ ФГБОУ ВО «СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ» Факультет: автоматизации и информационных технологий Кафедра: системотехники Курсовая работа 30 вариант Руководитель: Иванилова Т. Н. ____________________ дата оценка роспись Выполнил: Студент 1 курса, напр. 090301 _____ Кралич А.С. (подпись) _ (дата) Задание: Для произвольного неориентированного графа разработать алгоритм и составить программу позволяющую выделить в нём: цепь, цикл, простую цепь, простой цикл. Граф и количество рёбер в данных путях – входные параметры. Некоторые определения: Цепь – незамкнутый путь, в котором все рёбра попарно различны. Простая цепь - цепь, в которой все вершины попарно различны. Цикл - замкнутый путь, в котором все рёбра попарно различны. Простой цикл – цикл, в котором все вершины попарно различны. Алгоритм нахождения цепей, простых цепей, циклов, простых циклов:
Нужно помнить что: При нахождении цепи нельзя проходить по одному ребру несколько раз и начальная и конечная вершины не должны совпадать. При нахождении простой цепи нельзя попадать на одну вершину несколько раз. При нахождении цикла нельзя проходить по одному ребру несколько раз и начальная и конечная вершины должны совпадать. При нахождении простого цикла нельзя попадать на одну вершину несколько раз но начальная и конечная вершины должны совпадать. Код программы: program Kursovaja; {$APPTYPE CONSOLE} uses SysUtils; var A, A0: array[1..10, 1..10] of Integer; B: array[1..100] of Integer; I, J, K, N, M, M0, Z: Integer; procedure ProstajaSep; var I,J: Integer; begin M0:=M0+1; for I:=1 to N do begin B[M0]:=I; if A0[B[M0-1],B[M0]]=1 then if M0<>M then begin for J:=1 to N do A0[J,B[M0]]:=0; ProstajaSep; M0:=M0-1; for J:=1 to N do A0[J,B[M0]]:=A[J,B[M0]]; end else begin for J:=1 to M do Write(B[J],' '); Writeln; Z:=1; end; end; end; procedure Sep; var I,J: Integer; begin M0:=M0+1; for I:=1 to N do begin B[M0]:=I; if A0[B[M0-1],B[M0]]=1 then if M0<>M then begin A0[B[M0-1],B[M0]]:=0; A0[B[M0],B[M0-1]]:=0; Sep; M0:=M0-1; A0[B[M0-1],B[M0]]:=A[B[M0-1],B[M0]]; A0[B[M0],B[M0-1]]:=A[B[M0],B[M0-1]]; end else if B[1]<>B[M] then begin for J:=1 to M do Write(B[J],' '); Writeln; Z:=1; end; end; end; procedure ProstojSikl; var I,J: Integer; begin M0:=M0+1; for I:=1 to N do begin B[M0]:=I; if (M0=M) and (B[M-1]<>B[2]) and (M>2) then A0[B[M-1],B[1]]:=A[B[M-1],B[1]]; if A0[B[M0-1],B[M0]]=1 then if M0<>M then begin for J:=1 to N do A0[J,B[M0]]:=0; ProstojSikl; M0:=M0-1; for J:=1 to N do A0[J,B[M0]]:=A[J,B[M0]]; end else if B[1]=B[M] then begin for J:=1 to M do Write(B[J],' '); Writeln; Z:=1; end; if (M0=M) and (B[M-1]<>B[2]) and (M>2) then A0[B[M-1],B[1]]:=0; end; end; procedure Sikl; var I,J: Integer; begin M0:=M0+1; for I:=1 to N do begin B[M0]:=I; if A0[B[M0-1],B[M0]]=1 then if M0<>M then begin A0[B[M0-1],B[M0]]:=0; A0[B[M0],B[M0-1]]:=0; Sikl; M0:=M0-1; A0[B[M0-1],B[M0]]:=A[B[M0-1],B[M0]]; A0[B[M0],B[M0-1]]:=A[B[M0],B[M0-1]]; end else if B[1]=B[M] then begin for J:=1 to M do Write(B[J],' '); Writeln; Z:=1; end; end; end; begin repeat Writeln('Vvedom graf cherez matrisy smeznosti'); Write('Skolko versin y grafa(max 10): '); Readln(N); Writeln; Writeln('Iznachalno zapolnim matrisy smeznosti 0 ili 1?'); Write('Vas vibor: '); Readln(K); Writeln; if K=0 then for I:=1 to N do for J:=1 to N do A[I,J]:=0 else for I:=1 to N do for J:=1 to N do A[I,J]:=1; repeat Writeln('Sozdadim svazi versin grafov'); repeat Writeln; Writeln('Tekusaja matrisa smeznosti grafa:'); for I:=1 to N do begin for J:=1 to N do Write(A[I,J],' '); Writeln; end; Writeln; Writeln('Chto delaem?'); Writeln('1) Dobavim svaz'); Writeln('2) Ydalim svaz'); Writeln('3) Graf gotov'); Write('Vas vibor: '); Readln(K); if K=1 then begin Writeln; Writeln('Vvedite 1 versiny'); Readln(I); Writeln; Writeln('Vvedite 2 versiny'); Readln(J); A[I,J]:=1; A[J,I]:=1; end; if K=2 then begin Writeln; Writeln('Vvedite 1 versiny'); Readln(I); Writeln; Writeln('Vvedite 2 versiny'); Readln(J); A[I,J]:=0; A[J,I]:=0; end; until K=3; repeat Writeln; Writeln('Viberete sto nuzno naiti v grafe:'); Writeln('1) Prostiji sepi'); Writeln('2) Sepi'); Writeln('3) Prostiji sikli'); Writeln('4) Sikli'); Write('Vas vibor: '); Readln(K); Writeln; if K=1 then Write('Vvedite kolichistvo reber v prostih sepah: '); if K=2 then Write('Vvedite kolichistvo reber v sepah: '); if K=3 then Write('Vvedite kolichistvo reber v prostih siklah: '); if K=4 then Write('Vvedite kolichistvo reber v siklah: '); Readln(M); M:=M+1; Writeln; M0:=1; Z:=0; for I:=1 to N do for J:=1 to N do A0[I,J]:=A[I,J]; if K=1 then begin for I:=1 to N do begin B[M0]:=I; for J:=1 to N do A0[J,B[M0]]:=0; ProstajaSep; M0:=M0-1; for J:=1 to N do A0[J,B[M0]]:=A[J,B[M0]]; end; if Z=0 then Writeln('Prostih sepei s ',M-1,' rebrami net'); end; if K=2 then begin for I:=1 to N do begin B[M0]:=I; Sep; M0:=M0-1; end; if Z=0 then Writeln('Sepei s ',M-1,' rebrami net'); end; if K=3 then begin for I:=1 to N do begin B[M0]:=I; if M>2 then for J:=1 to N do A0[J,B[M0]]:=0; ProstojSikl; M0:=M0-1; for J:=1 to N do A0[J,B[M0]]:=A[J,B[M0]]; end; if Z=0 then Writeln('Prostih siklov s ',M-1,' rebrami net'); end; if K=4 then begin for I:=1 to N do begin B[M0]:=I; Sikl; M0:=M0-1; end; if Z=0 then Writeln('Siklov s ',M-1,' rebrami net'); end; Writeln; Writeln('Chto dalshe:'); Writeln('1) Vvesti novij graf'); Writeln('2) Redaktirovat graf bez izmenenija kolisistva versin'); Writeln('3) Poisk v starom grafe'); Writeln('4) Vihod'); Write('Vas vibor: '); Readln(K); Writeln; until (K=1) or (K=2) or (K=4); until (K=1) or (K=4); until K=4; end. Заключение: Была разработана программа для поиска цепей, простых цепей, циклов, простых циклов. Мы научились работать в языке программирования Delphi, выполнять алгоритмы на языке Delphi. Библиографический список 1. Иванилова, Т. Н. Дискретная математика / Т. Н. Иванилова - Красноярск: СибГТУ, 2004. - 83 с. 2. Дантеман Дж., Мишел Д., Тейлор Д. Программирование в среде DELPHI. - Киев: DiaSoft, 1995. - 608 с |