Andragen » 05 ноя 2004, 10:24
Знакомая задачка
Нам препод когдато задал, кто решит томого от экзамена с 10 освобождает
В группе из 40 человек решил только я ,сдесь предоставленно решение при помощи реверсирования(перевое которое пришло мне в голову),но есть и другие методы, на сколько я помню я потом ещё до двух допёр,
Вот решение
Код: Выделить всё
#include<stdio.h>
#include<conio.h>
enum bool {true=1, false=0};//opredeliaem bolevii tip
struct Item //struktura opisivaiushiaia element spiska
{int elem;//element spiska
Item *next;//ukazateli na sleduiushii Item
Item(int cis){elem=cis;}//konstruktor
};
typedef Item *link;
//vozrahiet true esli iz elementa 'iz' dostupen 'el' i false v obratnom sluciae
bool ifdostijim(link iz, link el)
{
Item *y=iz;
while(y!=NULL)
{if(y==el)return true;//proveriaet esli adres 'iz' raven adresu 'el'
y=y->next;
}
return false;//vozrasiaem false esli element ne naiden
}
//reversiruem spisok i proveriaem esli posleduiushi element dostupen iz
//uje otreversirovanogo spiska, esli dostupen togda esti kolitso
//vozrashiaet true esli esti kolitso i false v obratnom sluciae
bool reversering(link &beg)
{link t,y=beg,r=NULL;
while(y!=NULL)
{t=y->next;
y->next=r;
r=y;
if(ifdostijim(y,t))
{ beg=y;
return true;
}
y=t;
}
beg=r;
return false;
}
//meniu
void Meniu()
{printf("%43s","MENIU");
printf("\n0)Vihod(Esc)");
printf("\n1)Proverka spiska a");
printf("\n2)Proverka spiska b");
}
void press()
{
printf("\nPress any key to continue...");
getch();
}
//nacialo programmi
void main()
{//opredeliem spisok s ciklom
Item a1(1),a2(2),a3(3),a4(4),a5(5),a6(6),*abeg;
//delaem sviazi i zatsiklivem 6 i 3 elementi
abeg=&a1;
a1.next=&a2;
a2.next=&a3;
a3.next=&a4;
a4.next=&a5;
a5.next=&a6;
a6.next=&a3;
//opredelim spisok bez tsikla
Item b1(1),b2(2),b3(3),b4(4),b5(5),b6(6),*bbeg;
//delaem sviazi i 6 element ukazivaet v NULL
bbeg=&b1;
b1.next=&b2;
b2.next=&b3;
b3.next=&b4;
b4.next=&b5;
b5.next=&b6;
b6.next=NULL;
char men=0;
do{clrscr();
Meniu();
men=getch();
switch(men){
case '1':clrscr();
if(reversering(abeg))
printf("Spisok bill zacolitsovan");
else printf("Spisok ne zakolitsovan");
press();
break;
case '2':clrscr();
if(reversering(bbeg))
printf("Spisok bill zacolitsovan");
else printf("Spisok ne zakolitsovan");
press();
break;
}
}while(!(men=='0'|| men==27));
clrscr();
printf("Press any key to exit...");
getch();
}
Знакомая задачка :)
Нам препод когдато задал, кто решит томого от экзамена с 10 освобождает :)
В группе из 40 человек решил только я ,сдесь предоставленно решение при помощи реверсирования(перевое которое пришло мне в голову),но есть и другие методы, на сколько я помню я потом ещё до двух допёр,
Вот решение
[code]
#include<stdio.h>
#include<conio.h>
enum bool {true=1, false=0};//opredeliaem bolevii tip
struct Item //struktura opisivaiushiaia element spiska
{int elem;//element spiska
Item *next;//ukazateli na sleduiushii Item
Item(int cis){elem=cis;}//konstruktor
};
typedef Item *link;
//vozrahiet true esli iz elementa 'iz' dostupen 'el' i false v obratnom sluciae
bool ifdostijim(link iz, link el)
{
Item *y=iz;
while(y!=NULL)
{if(y==el)return true;//proveriaet esli adres 'iz' raven adresu 'el'
y=y->next;
}
return false;//vozrasiaem false esli element ne naiden
}
//reversiruem spisok i proveriaem esli posleduiushi element dostupen iz
//uje otreversirovanogo spiska, esli dostupen togda esti kolitso
//vozrashiaet true esli esti kolitso i false v obratnom sluciae
bool reversering(link &beg)
{link t,y=beg,r=NULL;
while(y!=NULL)
{t=y->next;
y->next=r;
r=y;
if(ifdostijim(y,t))
{ beg=y;
return true;
}
y=t;
}
beg=r;
return false;
}
//meniu
void Meniu()
{printf("%43s","MENIU");
printf("\n0)Vihod(Esc)");
printf("\n1)Proverka spiska a");
printf("\n2)Proverka spiska b");
}
void press()
{
printf("\nPress any key to continue...");
getch();
}
//nacialo programmi
void main()
{//opredeliem spisok s ciklom
Item a1(1),a2(2),a3(3),a4(4),a5(5),a6(6),*abeg;
//delaem sviazi i zatsiklivem 6 i 3 elementi
abeg=&a1;
a1.next=&a2;
a2.next=&a3;
a3.next=&a4;
a4.next=&a5;
a5.next=&a6;
a6.next=&a3;
//opredelim spisok bez tsikla
Item b1(1),b2(2),b3(3),b4(4),b5(5),b6(6),*bbeg;
//delaem sviazi i 6 element ukazivaet v NULL
bbeg=&b1;
b1.next=&b2;
b2.next=&b3;
b3.next=&b4;
b4.next=&b5;
b5.next=&b6;
b6.next=NULL;
char men=0;
do{clrscr();
Meniu();
men=getch();
switch(men){
case '1':clrscr();
if(reversering(abeg))
printf("Spisok bill zacolitsovan");
else printf("Spisok ne zakolitsovan");
press();
break;
case '2':clrscr();
if(reversering(bbeg))
printf("Spisok bill zacolitsovan");
else printf("Spisok ne zakolitsovan");
press();
break;
}
}while(!(men=='0'|| men==27));
clrscr();
printf("Press any key to exit...");
getch();
}[/code]