| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
boro
Dołączył: 27 Lut 2007
Posty: 286
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
|
 Wysłany: Sob 19:12, 24 Lis 2007 Temat postu: Algorytmy - Laboratorium PS_1 |
|
|
Ma ktoś może pdf z zadaniami /zestaw 4/ ? Asia nie działa i nie mam skąd wziąć treści zadan z laborek. Proszę o przesłanie mi pdf na [link widoczny dla zalogowanych]
Z góry dzięki :]
Ostatnio zmieniony przez boro dnia Nie 21:44, 17 Lut 2008, w całości zmieniany 1 raz
|
|
| Powrót do góry |
|
 |
|
|
 |
vbazyl
Dołączył: 06 Mar 2007
Posty: 94
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
Skąd: Podlasie
|
| Wysłany: Czw 21:11, 29 Lis 2007 Temat postu: |
|
|
A może ktoś wpadł na pomysł rozwiązania dyskretnego problemu plecakowego? Bo ja coś tam wymyśliłem, ale dla najgorszego przypadku obliczyłem, że rozwiązanie tego zajmie jakieś...1000 lat :P
Tak więc proszę o podrzucenie pomysłu (najlepiej pomysł + kod hehe;)
|
|
| Powrót do góry |
|
|
boro
Dołączył: 27 Lut 2007
Posty: 286
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
|
| Wysłany: Nie 12:29, 02 Gru 2007 Temat postu: |
|
|
Mam problem bo zupelnie nie wiem jak zabrac sie do zadania ktore zamieszczam ponizej. Moze ma ktos jakis pomysl jak to rozwiazac?
Zadanie 4
Grupa ambitnych studentów III roku wydziału informatyki chce złamać pewien szyfr i potrzebny jest im
najszybszy algorytm rozwiązujący następujący problem. Dane są dwa ciągi znaków A i B. Należy znaleźć
możliwie najdłuższy ciąg znaków występujący w obydwu ciągach A i B.
Napisz program, który:
1. Wczyta z pliku in4.txt długości ciągów A i B oraz elementy tych ciągów
2. Wyznaczy długość najdłuższego ciągu znaków i wpisze tą długość oraz ten ciąg do pliku out4.txt (jeśli jest kilka takich ciągów to wystarczy wypisać jeden)
Wejście:
W pierwszym wierszu pliku in4.txt znajdują się dwie liczby całkowite oddzielone pojedynczą spacją n1 n2 oznaczające długości ciągów(n1, n2≤ 256). W kolejnych dwóch liniach tego pliku znajdują się ciągi znaków A i
B.
Wyjście:
W pliku out4.txt w pierwszej jego linii jest wpisywana liczba całkowita, która oznacza długość najdłuższego ciągu występującego w obydwu zbiorach A i B. W kolejnej linii wypisywany jest ten ciąg znaków
Przykład 1:
Dla następującego pliku in4.txt
12 7
POLITECHNIKA
TOALETA
Plik out4.txt wygląda następująco:
OLTA
|
|
| Powrót do góry |
|
|
czart
Dołączył: 02 Mar 2007
Posty: 168
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
Skąd: Z lasu
|
| Wysłany: Nie 13:46, 02 Gru 2007 Temat postu: |
|
|
Ja mam podobny problem z zadaniem nr 1 . Nie wiem jak to ugryźć. Oba te zadania chyba podpadają pod programowanie dynamiczne którego do końca nie umiem zastasować  . Sypnie ktoś pomysłem :>
|
|
| Powrót do góry |
|
|
wicher
Dołączył: 07 Mar 2007
Posty: 70
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
Skąd: z 13 posterunku
|
| Wysłany: Nie 14:39, 02 Gru 2007 Temat postu: |
|
|
Najlepiej żeby ktoś, kto ma cokolwiek (pomysł, algorytm, kod programu), podzielił się swoimi spostrzeżeniami na forum. Nie tylko do zadania 1 i 4 ale do wszystkich zadań. Wtedy metodą prób i błędów dojdziemy do poprawnych algorytmów.
Co do zadania 4 to nie rozumiem za bardzo co miała na myśli. Jeśli ciąg oznacza dowolny "zlepek" znaków to moim zdaniem ciągi A i B można posortować, później porównując elementy z A i B wyszukać ten najdłuższy ciąg. Problem w tym, że proste porównania dają duży koszt algorytmu. Czyli tak na dobrą sprawę nic dobrego nie wymyśliłem.
|
|
| Powrót do góry |
|
|
vbazyl
Dołączył: 06 Mar 2007
Posty: 94
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
Skąd: Podlasie
|
| Wysłany: Nie 16:56, 02 Gru 2007 Temat postu: |
|
|
Tu są pewne pomysły do zad. 1 ;]
[link widoczny dla zalogowanych]*&_%3Ali=*&p=1
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
A to mój kod w cpp, ale nie wiem teraz jak sprawdzić, które przedmioty zostały wybrane (wypisuje tylko max wartość plecaka,czekam na pomysły):
Edit: Kod został poprawiony i działa wszystko.
| Kod: |
class Ladunek
{
public:
int w; //waga
int c; //cena
Ladunek()
{
w=0;
c=0;
};
};
void rozwiazanie1()
{
Ladunek gtab[21];
int N=0,K=0;
wczytaj_z_pliku(gtab,N,K);
int V[N+1][K+1];
int i,j,pp;
V[0][0]=0;
for(i=1;i<=K;i++)
V[0][i]=-1;
for(i=1;i<=N;i++)
for(j=0;j<=K;j++)
{
pp=j-gtab[i].w;
if ((pp<0) || (V[i-1][pp]<0))
V[i][j]=V[i-1][j];
else
V[i][j]=max(V[i-1][pp]+gtab[i].c,V[i-1][j]);
};
int max=0;
for(j=0;j<=K;j++)
{
if( V[N][j]>V[N][max])
max=j;
};
ofstream wy1("out1.txt"); //otworzenie pliku do zapisu
i=N;
j=max;
int ptab[N];
int z=0;
while(j) //tutaj szuka nr użytych przedmiotów
{ //i zapisuje je do tablicy ptab
if(V[i][j]!=V[i-1][j])
{
j-=gtab[i].w;
ptab[z]=i;
z++;
};
--i;
};
for(i=z-1;i>=0;i--) //przedmioty są wpisane "od tyłu" więc i tak je
wy1<<ptab[i]<<" "; //odczytujemy z ptab i zapisujemy do pliku wy1
wy1<<endl;
wy1<<V[N][max]; //a tu jest maksymalna wartość tych przedmiotów
}; |
Ostatnio zmieniony przez vbazyl dnia Pon 0:59, 03 Gru 2007, w całości zmieniany 9 razy
|
|
| Powrót do góry |
|
|
dynio
Dołączył: 07 Mar 2007
Posty: 7
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
|
| Wysłany: Nie 21:20, 02 Gru 2007 Temat postu: |
|
|
|
a może by ten projekt przełożyć na nast. tydzień ??
|
|
| Powrót do góry |
|
|
boro
Dołączył: 27 Lut 2007
Posty: 286
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
|
| Wysłany: Nie 21:24, 02 Gru 2007 Temat postu: |
|
|
|
mozna byloby sprobowac ale nie wiem czy to przejdzie. raz juz byl przelozony projekt. poza tym ostatnio mowila ze jestesmy do tylu z programami. no chyba ze sporo osob nie bedzie mialo dokonczonych programow wtedy mozna cos pokombinowac.
|
|
| Powrót do góry |
|
|
vbazyl
Dołączył: 06 Mar 2007
Posty: 94
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
Skąd: Podlasie
|
| Wysłany: Nie 21:53, 02 Gru 2007 Temat postu: |
|
|
|
Haha! Mam! ;] Chcecie? To popatrzcie na mój poprzedni post.
|
|
| Powrót do góry |
|
|
czart
Dołączył: 02 Mar 2007
Posty: 168
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
Skąd: Z lasu
|
| Wysłany: Nie 23:28, 02 Gru 2007 Temat postu: |
|
|
Hej bazyl, wszystko spoko, ale gdzie wypisujesz elementy ktore tworza wynik ...
Reszte sam zrobilem, ale wlasnie nie moge sobie poradzic ze znalezieniem tych elementow :] (juz po obliczeniu najwiekszej wartosci)
|
|
| Powrót do góry |
|
|
chodor
Dołączył: 28 Lut 2007
Posty: 6
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
|
| Wysłany: Pon 0:20, 03 Gru 2007 Temat postu: |
|
|
|
u mnie ten sam problem niestety;/ i juz nie mam pomyslu jak to zrobic;/ moze cos sie do jutra wymysli noc przeciez dluga:)
|
|
| Powrót do góry |
|
|
vbazyl
Dołączył: 06 Mar 2007
Posty: 94
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
Skąd: Podlasie
|
| Wysłany: Pon 0:55, 03 Gru 2007 Temat postu: |
|
|
Już zamieściłem stosowne wyjaśnienia w kodzie. A te elementy najpierw zapisuję do tablicy ptab, a później do pliku wy1.
Trzeba dodać bibliotekę <fstream> która obsługuje pliki.
|
|
| Powrót do góry |
|
|
czart
Dołączył: 02 Mar 2007
Posty: 168
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
Skąd: Z lasu
|
| Wysłany: Nie 15:04, 09 Gru 2007 Temat postu: |
|
|
| Kod: | while(j) //tutaj szuka nr użytych przedmiotów
{ //i zapisuje je do tablicy ptab
if(V[i][j]!=V[i-1][j])
{
j-=gtab[i].w;
ptab[z]=i;
z++;
};
--i;
}; |
Wydaje mi się ze ten kod jest bledny. Naprawde on u ciebie dziala ? Po pierwsze taka konstrukcja while zwiesza mi program :I. while(j>0) wyglada sensowniej.
Dalej zamiast j-=gtab[i].w; powinno byc j-=gtab[i-1].w; gtab ma najwiekszy indeks N-1 a i na poczatku wynosi N.
Reszta ok.
|
|
| Powrót do góry |
|
|
vbazyl
Dołączył: 06 Mar 2007
Posty: 94
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
Skąd: Podlasie
|
| Wysłany: Nie 18:10, 09 Gru 2007 Temat postu: |
|
|
No mi to działa dobrze. A zwróć uwagę,że mam pętlę
trochę to dziwnie wygląda, ale u mnie program działa.
A co do pętli
to j jest ta nasza waga, którą umieściliśmy w plecaku i teraz szukamy wag, których użyliśmy i odejmujemy je od j. I gdy wszystkie wagi znajdziemy to j nie może być przecież ujemne, ale równe 0.
Aha już wyczaiłem czemu masz błąd. To jest moja funkcja wczytująca plik do tablicy (zwróć uwagę, że indeksuję nie od 0, ale od 1):
| Kod: |
void wczytaj_z_pliku(Ladunek tab[],int &N,int &K)
{
ifstream we("in1.txt");
if(!we) cout<<"Blad!"<<endl;
we>>N; // N<=20
we>>K; // K<=100
for(int i=1;i<=N;i++)
{
we>>tab[i].w;
we>>tab[i].c;
};
}; |
|
|
| Powrót do góry |
|
|
czart
Dołączył: 02 Mar 2007
Posty: 168
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
Skąd: Z lasu
|
| Wysłany: Nie 18:55, 09 Gru 2007 Temat postu: |
|
|
I wszystko jasne, ja indeksuje od 0 i stad te rozbieznosci;]
Z whilem to moj blad byl, jednak dobrze wszystko masz.
|
|
| Powrót do góry |
|
|
