Определить способы возможной связи между двумя заданными спутниками - C (СИ)
Формулировка задачи:
Кто сможет перевести из pascal в c.
Или предложить вариант получше в c.
{ В космическом центре проектируется систем организции связи
между спутникми, действующейя в реальном масштабе времени. Каждый
спутник может иметь либо не иметь как радиостанцию, так и приемник
радиосигналов. Сигналы с одного спутника могут передаваться на другие
через произвольное число промежуточных спутников. Заранее известно,
когда два спутника появляются в зоне радиовидимости и в течение какого
времени спутники будут находиться в этой зоне. Требуется определить
способы возможной связи между двумя заданными спутниками в указанный
момент времени с минимальным числом промежуточных звеньев.}
Program Cosmos;
Uses crt;
Const
max=10;
Type
bukvs= set of 0..255;
mat=array[1..max,1..max] of integer; { матрица смежности }
put=1..max; { номер вершины в пути }
sputik= record
name:string;
r:byte;
p:byte;
end;
Vrem= record
time1:integer;
time2:integer;
end;
Tim= array[1..max,1..max] of vrem; { матрица сеансов связи}
sput= array[1..max] of sputik;
const Cif: bukvs=[48..57];
Var
matr : mat;
Ti:tim;
sp:sput;
m: set of put; { множество вершин, входящих в путь }
rev: array [1..max] of integer;
gr: array [1..max] of integer; { текущий путь }
a,b,ver,j,i,vr1,vr2,error,times,t: integer;
k,kk,flag,maxi,maxj,ff,fl,min,lag:byte;
l: boolean;
ch,c: char;
t1, t2:text;
s1,s2,name1,name2:string;
Procedure Sozd;
Begin
k:=1;
While not EOF(t1) do
Begin
inc(kk);
Begin
k:=1;
s1[0]:=#0;
s1[0]:=#255;
delete(s1,0,200);
s1[0]:=#255;
While ord(ch)<>32 do
Begin
Read(t1,ch);
if ord(ch)<>32 then
s1[k]:=ch;
inc(k);
End;
delete(s1,(k-1),255);
sp[kk].name:=s1;
k:=1;
read(t1,ch);
If ch='+' then
sp[kk].r:=1
Else
If ch='-' then
sp[kk].r:=0
Else
Begin
clrscr;
ff:=1;
textcolor(4);
Writeln('Вы неправильно ввели информацию в 1 исходном файле. ');
textcolor(4+128);
Write('НАЖМИТЕ Enter');
readln;
Close(t1);
Close(t2);
exit;
End;
read(t1,ch);
read(t1,ch);
If ch='+' then
sp[kk].p:=1
Else
If ch='-' then
sp[kk].p:=0
Else
Begin
clrscr;
ff:=1;
textcolor(4);
Writeln('Вы неправильно ввели информацию в 1 исходном файле. ');
textcolor(4+128);
Write('НАЖМИТЕ Enter');
readln;
Close(t1);
Close(t2);
exit;
End;
readln(t1,s1);
End;
End;
ver:=kk;
ff:=0;
End;
Procedure Sozd2;
Begin
While not EOF(t2) do
Begin
{While not (Eof(t2)) or (eoln) do}
Begin
k:=1;
flag:=0;
k:=0;
s1[k]:='0';
s1[k]:=#255;
delete(s1,0,40);
delete(s1,1,254);
s1[k]:=#255;
k:=1;
s1[k]:=#0;
While ord(ch)<>32 do
Begin
Read(t2,ch);
if ord(ch)<>32 then
s1[k]:=ch;
inc(k);
End;
delete(s1,(k-1),255);
For i:=1 to ver do
If sp[i].name=s1 then
begin
inc(flag);
maxi:=i;
end;
If flag<>1 then
Begin
clrscr;
ff:=1;
textcolor(4);
ff:=1;
Writeln('Вы неправильно ввели информацию в 1 или 2 исходном файле. ');
textcolor(4+128);
Write('НАЖМИТЕ Enter');
readln;
Close(t1);
Close(t2);
exit;
End;
k:=1;
flag:=0;
s2[0]:=#255;
ch:='0';
While ord(ch)<>32 do
Begin
Read(t2,ch);
if ord(ch)<>32 then
s2[k]:=ch;
inc(k);
End;
delete(s2,(k-1),255);
For i:=1 to ver do
If sp[i].name=s2 then
begin
inc(flag);
maxj:=i;
end;
If flag<>1 then
Begin
clrscr;
ff:=1;
textcolor(4);
Writeln('Вы неправильно ввели информацию в 1 или 2 исходном файле. ');
textcolor(4+128);
Write('НАЖМИТЕ Enter');
readln;
Close(t1);
Close(t2);
exit;
End;
If S1=s2 then
Begin
clrscr;
textcolor(4);
ff:=1;
Writeln('Вы неправильно ввели информацию во 2 исходном файле. ');
Writeln('Программа будет закрыта после нажатия клавищи Enter.');
textcolor(4+128);
Write('НАЖМИТЕ Enter');
readln;
Close(t1);
Close(t2);
exit;
End;
k:=1;
For kk:=1 to 5 do
begin
Read(t2,ch);
If ord(ch) in cif then
begin
s1[k]:=ch;
inc(k);
end;
if kk=3 then
begin
delete(s1,3,253);
val(s1,vr1,error);
delete(s1,0,256);
s1[0]:=#255;
k:=1;
end;
if kk=5 then
begin
vr1:=vr1*60;
delete(s1,3,253);
val(s1,vr2,error);
ti[maxi,maxj].time1:=vr1+vr2;
ti[maxj,maxi].time1:=vr1+vr2;
end;
if (kk=5) and (k<3) then
Begin
clrscr;
textcolor(4);
ff:=1;
Writeln('Вы неправильно ввели информацию во 2 исходном файле. ');
textcolor(4+128);
Write('НАЖМИТЕ Enter');
readln;
Close(t1);
Close(t2);
exit;
End;
end;
k:=1;
read(t2,ch);
For kk:=1 to 5 do
begin
Read(t2,ch);
If ord(ch) in cif then
begin
s1[k]:=ch;
inc(k);
end;
if kk=3 then
begin
delete(s1,3,253);
val(s1,vr1,error);
delete(s1,0,256);
s1[0]:=#255;
k:=1;
end;
if kk=5 then
begin
vr1:=vr1*60;
delete(s1,3,253);
val(s1,vr2,error);
ti[maxi,maxj].time2:=vr1+vr2;
ti[maxj,maxi].time2:=vr1+vr2;
end;
if (kk=5) and (k<3) then
Begin
clrscr;
textcolor(4);
ff:=1;
Writeln('Вы неправильно ввели информацию во 2 исходном файле. ');
textcolor(4+128);
Write('НАЖМИТЕ Enter');
readln;
Close(t1);
Close(t2);
exit;
End;
End;
{while not(eof(t2)) or (eoln) do}
readln(t2,s2);
End;
End;
End;
Procedure PoiskPut(t: integer);
{ поиск всех путей на графе }
Var i: integer;
Begin
gr[j]:=t; { добавление в путь текущей вершины }
m:=m+[t]; { коррекция множества вершин пути }
j:=j+1;
if t=maxj then { maxj-конечная вершина }
begin
{Writeln('Найден путь: ');}
if min>j then
begin
min:=j;
lag:=1;
For i:=1 to max do
rev[i]:=0;
For i:=1 to j-1 do { вывод пути }
rev[i]:=gr[i];
end;
end
else
For i:=1 to ver do
if not (i in m) and (ti[t,i].time1<>9999) and (ti[t,i].time2<>9999) then
if (ti[t,i].time1<times) and (ti[t,i].time2>times) then
{ поиск в глубину: выбор продолжения пути без цикла }
{if (sp[i].p=1) and (sp[t].r=1 ) then}
PoiskPut(i);
{ здесь оказываемся после нахождения очередного пути }
{ или в случае попадания в тупик }
m:=m-[t];
{ исключение из множества вершин пути последней вершины }
j:=j-1 { возврат в предыдущую вершину }
End;
BEGIN
clrscr;
ff:=2;
For i:=1 to max do
For j:=1 to max do
begin
ti[i,j].time1:=9999;
ti[i,j].time2:=9999;
end;
While ff<>0 do Begin
While fl<>2 do
Begin
textcolor(15);
Writeln('Укажите адреса двух исходных файлов. В первом - имена спутников и их');
Writeln('характеристики(наличие или отсутствие приемника и радиостанции), а во');
Writeln('втором приведено расписание сеансов связи спутников.');
Write('Введите путь к первому файлу: ');
Readln(s1);
if ord(s1[1])<>0 then
begin
Assign(t1,s1);
{$I-}
RESEt (t1);
{$I+}
If IOResult=0 then
begin
Write('Введите путь ко второму файлу: ');
Readln(s1);
if ord(s1[1])<>0 then
begin
Assign(t2,s1);
{$I-}
RESEt (t2);
{$I+}
If IOResult=0 then
fl:=2
else
Begin
clrscr;
textcolor(4);
Writeln('Вы неправильно ввели адрес 2 исходного файла. ');
textcolor(4+128);
Write('НАЖМИТЕ Enter');
readln;
Close(t1);
flag:=0;
End;
End
Else
begin
Textcolor(4);
Writeln('Вы не указали адрес 2 исходника программы.');
Writeln('Нажмите Enter.');
Readln;
Close(t1);
end;
End
Else
Begin
clrscr;
textcolor(4);
Writeln('Вы неправильно ввели адрес 1 исходного файла. ');
textcolor(4+128);
Write('НАЖМИТЕ Enter');
readln;
End;
End
Else
begin
Textcolor(4);
Writeln('Вы не указали адрес 1 исходника программы.');
Writeln('Нажмите Enter.');
Readln;
end;
End;
Writeln('');
Sozd;
if ff=0 then
Sozd2;
if ff=1 then
halt;
End;
Writeln('Все данные введены правильно!');
While c<>'2' do
Begin
clrscr;
textcolor(15);
lag:=0;
min:=max;
Writeln('МЕНЮ:');
Writeln('1-поиск наименьшего пути между двумя спутниками');
Writeln('2-выход из программы');
Readln(c);
case (c) of '1' :
Begin
clrscr;
name1[0]:=#255;
name2[0]:=#255;
flag:=0;
Write('Введите название источника сигнала(имя спутника): ');
Readln(name1);
For i:=1 to ver do
If sp[i].name=name1 then
begin
inc(flag);
maxi:=i;
end;
If flag=1 then
Begin
Write('Введите название приемника сигнала(имя спутника): ');
Readln(name2);
For i:=1 to ver do
If sp[i].name=name2 then
begin
inc(flag);
maxj:=i;
end;
If flag=2 then
Begin
Write('Введите время связи: ');
Readln(s2);
k:=1;
For kk:=1 to 5 do
Begin
ch:=s2[kk];
If ord(ch) in cif then
begin
s1[k]:=ch;
inc(k);
end;
If kk=3 then
begin
delete(s1,3,253);
val(s1,vr1,error);
delete(s1,0,256);
s1[0]:=#255;
k:=1;
end;
If kk=5 then
begin
vr1:=vr1*60;
delete(s1,3,253);
val(s1,vr2,error);
times:=vr1+vr2;
end;
End;
If (kk=5) and (k>=3) then
Begin
{ End;}
If sp[maxi].r=1 then
Begin
If sp[maxj].p=1 then
begin
t:=0;
j:=1;
i:=0;
m:=[];
PoiskPut(maxi);
end
Else
Begin
clrscr;
textcolor(4);
Writeln('Передача невозможна так как на 2 спутнике нет приемника.');
textcolor(4+128);
Write('НАЖМИТЕ Enter');
readln;
End;
End
Else
Begin
clrscr;
textcolor(4);
Writeln('Передача невозможна так как на 1 спутнике нет передатчика.');
textcolor(4+128);
Write('НАЖМИТЕ Enter');
readln;
End;
End
Else
Begin
clrscr;
textcolor(4);
Writeln('Вы неправильно ввели время связи. ');
Writeln('Программа будет закрыта после нажатия клавищи Enter.');
textcolor(4+128);
Write('НАЖМИТЕ Enter');
readln;
End;
end
Else
Begin
clrscr;
textcolor(4);
Writeln('Вы неправильно ввели имя второго спутника. ');
Writeln('Программа будет закрыта после нажатия клавищи Enter.');
textcolor(4+128);
Write('НАЖМИТЕ Enter');
readln;
End;
end
Else
Begin
clrscr;
textcolor(4);
Writeln('Вы неправильно ввели имя первого спутника. ');
Writeln('Программа будет закрыта после нажатия клавищи Enter.');
textcolor(4+128);
Write('НАЖМИТЕ Enter');
readln;
End;
textcolor(15);
If lag=1 then
Begin
Writeln('Найден минимальный путь.');
For i:=1 to min-1 do
writeln(sp[rev[i]].name);
end
else
Writeln('При заданных вами условиях, связь установить невозможно.');
readln;
end;
'2':
begin
Close(t1);
Close(t2);
end;
End;
end;
END.Решение задачи: «Определить способы возможной связи между двумя заданными спутниками»
textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define MAX 10
// информация о спутнике
struct sputnik
{
char name[32]; //название спутника
int r; // наличие передатчика на спутнике
int p; // наличие приемника на спутнике
};
struct vrem
{
int time1;
int time2;
};
struct vrem** ti;
struct sputnik* sp;
int **matr;
int *put;
int *rev;
int *gr;
int a,b,ver,j,i,vr1,vr2,error, times,t;
int k, kk, flag, maxi, maxj, ff, fl, min, lag;
int l;
char ch, c;
int cnt;
char b1[20], b2[20], b3[20], b4[20], b5[20], b6[20], s1[20], s2[20], name1[20], name2[20], t1[20], t2[20];
char tine[20];
void sozd();
void sozd2();
void PoiskPut(int times, int t1, int t2);
void create_arrays();
void free_arrays();
int main()
{
int f;
int times;
int state;
int i, j;
int i1, i2;
char c;
f = 0;
create_arrays();
for(i = 0; i < MAX; i++)
for(j = 0; j < MAX; j++)
{
ti[i][j].time1 = -1;
ti[i][j].time2 = -1;
}
printf("Укажите адреса двух исходных файлов. В первом - имена спутников и их характеристики(наличие или отсутствие приемника и радиостанции), а во втором приведено расписание сеансов связи спутников. Введите путь к первому файлу: ");
scanf("%s", &s1);
printf("Введите путь ко второму файлу: ");
scanf("%s", &s2);
sozd(); //чтение из первого файла
sozd2(); //чтение из второго файла
do
{
printf("МЕНЮ:\n1-поиск наименьшего пути между двумя спутниками\n2-выход из программы\n");
scanf("%c", &c);
switch(c)
{
case '1':
printf("Введите название источника сигнала(имя спутника): ");
scanf("%s", &name1);
for(j=0;j< ver;j++)
if ( !strcmp( name1, sp[j].name))
f = 1, i1 = j;
if (f == 0) printf("Вы неправильно ввели имя первого спутника.\n"); else f = 0;
printf("Введите название приемника сигнала(имя спутника): ");
scanf("%s", &name2);
for(j=0;j< ver;j++)
if ( !strcmp( name2, sp[j].name))
f = 1, i2 = j;
if (f == 0) printf("Вы неправильно ввели имя второго спутника.\n"); else f = 0;
printf("Введите время связи: ");
scanf("%s", &tine);
{
state = 0; i = 0;
for(j = 0; state != 2 && j < 20; j++)
{
switch(state)
{
case 0:
switch(tine[j])
{
case ':': b3[i] = '\0'; i++; i = 0; state = 1; break;
default: b3[i] = tine[j]; i++; break;
}
break;
case 1:
switch(tine[j])
{
case '\0':
b4[i] = '\0';
state = 2;
times = 60 * atoi(b3) + atoi(b4);
if (sp[i1].r == 1)
{
if (sp[i2].p == 1)
cnt = 0, PoiskPut(times, i1, i2);
else printf("Передача невозможна так как на 2 спутнике нет приемника.\n");
}
else printf("Передача невозможна так как на 1 спутнике нет передатчика.\n");
break;
default: b4[i] = tine[j]; i++; break;
}
break;
}
}
}
break;
case '2':
exit(0);
break;
}
} while (c != '2');
free_arrays();
return 0;
}
/*
считывание файла с данными о спутниках:
(название спутника) (наличие передатчика на спутнике) (наличие приемника на спутнике)
*/
void sozd()
{
FILE *f;
char ch;
int state;
int i;
i = 0;
state = 0;
printf("%s", s1);
f = fopen(s1, "r"); printf("\n");
while((ch = fgetc(f)) != EOF )
{
//printf("%d %c\n", state, ch);
switch (state)
{
case 0:
switch(ch)
{
case '\xd': case '\xa': break;
case '\x20': sp[kk].name[i] = '\0'; state = 1; break;
default: sp[kk].name[i] = ch; i++; break;
}
break;
case 1:
switch(ch)
{
case '\x20': break;
case '+': sp[kk].r = 1; state = 2; break;
case '-': sp[kk].r = 0; state = 2; break;
default: printf("Вы неправильно ввели информацию в 1 исходном файле.\n"); exit(0); break;
}
break;
case 2:
{
switch(ch)
{
case '\x20': break;
case '+': sp[kk].p = 1; state = 0; i = 0; kk++; break;
case '-': sp[kk].p = 0; state = 0; i = 0; kk++; break;
default: printf("Вы неправильно ввели информацию в 1 исходном файле.\n"); exit(0); break;
}
}
break;
}
}
fclose(f);
for(i=0;i<kk;i++)
printf("name: %s r:%d p:%d\n", sp[i].name, sp[i].r, sp[i].p);
ver = kk;
}
/*
считывание файла с данными о времени связи:
(название 1 спутника) (название 2 спутника) (час начала связи):(минута) (час окончания связи):(минута)
*/
void sozd2()
{
int i1, i2;
FILE *f;
char ch;
int state;
int i;
int j;
int times;
i = 0;
state = 0;
printf("%s", s2);
f = fopen(s2, "r"); printf("\n");
while((ch = fgetc(f)) != EOF )
{
//printf("%d %c\n", state, ch);
switch (state)
{
case 0:
switch(ch)
{
case '\xd': case '\xa': break;
case '\x20':
b1[i] = '\0'; i = 0; state = 1;
for(j=0;j< ver;j++)
if ( !strcmp( b1, sp[j].name))
i1 = j;
break;
default: b1[i] = ch; i++; break;
}
break;
case 1:
switch(ch)
{
case '\xd': case '\xa': break;
case '\x20': break;
default: b2[i] = ch; i++; state = 2; break;
}
break;
case 2:
switch(ch)
{
case '\xd': case '\xa': break;
case '\x20':
b2[i] = '\0'; i = 0; state = 3;
for(j=0;j< ver;j++)
if ( !strcmp( b2, sp[j].name))
i2 = j;
break;
default: b2[i] = ch; i++; break;
}
break;
case 3:
switch(ch)
{
case '\xd': case '\xa': case '\x20': break;
default: b3[i] = ch; i++; state = 4; break;
}
break;
case 4:
switch(ch)
{
case ':': b3[i] = '\0'; i = 0; state = 5; break;
case '\x20': break;
default: b3[i] = ch; i++; break;
}
break;
case 5:
switch(ch)
{
case '\xd': case '\xa': case '\x20': break;
default: b4[i] = ch; i++; state = 6; break;
}
break;
case 6:
switch(ch)
{
case '\xd': case '\xa': break;
case '\x20': b4[i] = '\0'; i = 0; state = 7; break;
default: b4[i] = ch; i++; break;
}
break;
case 7:
switch(ch)
{
case '\xd': case '\xa': case '\x20': break;
default: b5[i] = ch; i++; state = 8; break;
}
break;
case 8:
switch(ch)
{
case ':': b5[i] = '\0'; i = 0; state = 9; break;
case '\x20': break;
default: b5[i] = ch; i++; break;
}
break;
case 9:
switch(ch)
{
case '\xd': case '\xa': case '\x20': break;
default: b6[i] = ch; i++; state = 10; break;
}
break;
case 10:
switch(ch)
{
case '\xd': case '\xa':
b6[i] = '\0'; i = 0; state = 0;
times = 60 * atoi(b3) + atoi(b4); ti[i1][i2].time1 = times;
times = 60 * atoi(b5) + atoi(b6); ti[i1][i2].time2 = times;
//printf("%d %d %d %d \n" , atoi(b3),atoi(b4),atoi(b5),atoi(b6));
break;
case '\x20': break;
default: b6[i] = ch; i++; break;
}
break;
}
}
fclose(f);
}
// поиск всех путей на графе
void PoiskPut(int times, int t1, int t2)
{
int f;
printf("PoiskPut: \n");
f = 0;
gr[cnt] = t1;
cnt++;
if (t1 == t2)
{
printf("Найден путь: \n");
for(k=0;k<cnt;k++)
printf("%d ", k);
printf("\n");
}
else
for(j=0;j<ver;j++)
{
for(f=0, k=0;k<cnt;k++)
{
if (j == gr[k])
f = 1;
}
if (f == 0 && ti[t1][j].time1 != -1 && ti[t1][j].time2 != -1)
if ( ti[t1][j].time1 < times && ti[t1][j].time2 > times )
PoiskPut(times, j, t2);
}
cnt--;
}
void create_arrays()
{
int i;
sp = (struct sputnik*) malloc(MAX * sizeof(struct sputnik));
rev = (int*) malloc(MAX * sizeof(int));
gr = (int*) malloc(MAX * sizeof(int));
ti = (struct vrem** ) malloc(MAX * sizeof(struct vrem*));
matr = (int**) malloc(MAX * sizeof(int*));
for(i = 0; i < MAX; i++)
{
ti[i] = (struct vrem*) malloc(MAX * sizeof(struct vrem));
matr[i] = (int*) malloc(MAX * sizeof(int));
}
}
void free_arrays()
{
int i;
for(i = 0; i < MAX; i++)
{
free(ti[i]);
free(matr[i]);
}
free(rev);
free(gr);
free(ti);
free(matr);
free(sp);
}