Zadanie maturalne 4.3 wega 2018

0

W ramach projektu WEGA naukowcom udało się odczytać sygnały radiowe pochodzące
z przestrzeni kosmicznej. Po wstępnej obróbce zapisali je do pliku sygnaly.txt.
W pliku sygnaly.txt znajduje się 1000 wierszy. Każdy wiersz zawiera jedno niepuste
słowo złożone z wielkich liter alfabetu angielskiego. Długość jednego słowa nie przekracza 100
znaków.
Napisz program(y), który(e) da(dzą) odpowiedzi do poniższych zadań. Odpowiedzi zapisz
w pliku wyniki4.txt, a każdą odpowiedź poprzedź numerem oznaczającym odpowiednie
zadanie.
Uwaga: Plik przyklad.txt zawiera dane przykładowe spełniające warunki zadania.
Odpowiedzi dla danych z pliku przyklad.txt są podane pod pytaniami.
A teraz zadanie 4.3
W tym zadaniu rozważmy odległość liter w alfabecie – np. litery A i B są od siebie oddalone
o 1, A i E o 4, F i D o 2, a każda litera od siebie samej jest oddalona o 0. Wypisz wszystkie
słowa, w których każde dwie litery oddalone są od siebie w alfabecie co najwyżej o 10. Słowa
wypisz w kolejności występowania w pliku sygnaly.txt, po jednym w wierszu.
Na przykład CGECF jest takim słowem, ale ABEZA nie jest (odległość A – Z wynosi 25).
I pytanie - dlaczego mój kod nie działa?



#include <iostream>
#include <fstream>
using namespace std;
int main()
{ ifstream wejscie;
ofstream wyjscie;
string t[1000];
wejscie.open("sygnaly.txt");
for (int i=0; i<1000; i++)
{
wejscie >> t[i];
}
wejscie.close();
for (int z=0; z<1000; z++) //przeszukiwanie słów	
{   
     for(int x=0; x<(t[z].length()-1)*2;  x++)
     	for(int k=t[z].length();  k>=0;    k--)
		if(t[z][x]-t[z][   k   ]<11 or t[z][x]-t[z][k]  >-11 )
		{
			cout<<t[z];
		}
	}
system("pause");	
}

I tak, wiem że kod nie jest optymalny, bo optymalne porównanie nie porównuje dwa razy tych samych danych w tablicy tylko w odwróconej kolejności. Ale to nie działa w ogóle jak powinno.

1

Dla k == t[z].length() nie istnieje element t[z][k], ostatni element to t[z][t[z].length() - 1]
A x to już w ogóle ma jakieś kosmiczne wartości, (t[z].length() - 1) * 2 wychodzi daaaaleko poza tablicę.

Swoją drogą sformatuj kod, bo brzydko sformatowany kod trudniej zrozumieć i łatwiej o błąd.

0
twonek napisał(a):

Dla k == t[z].length() nie istnieje element t[z][k], ostatni element to t[z][t[z].length() - 1]
A x to już w ogóle ma jakieś kosmiczne wartości, (t[z].length() - 1) * 2 wychodzi daaaaleko poza tablicę.

Swoją drogą sformatuj kod, bo brzydko sformatowany kod trudniej zrozumieć i łatwiej o błąd.
Poprawiłam, ale dalej nijak nie wychodzi - przepraszam jeśli wyszedł debilizm, czy coś.

{   
for(int x=0; x<t[z].length()-1;  x++)
for(int k=t[z].length();  k>=0;    k--)
if(t[z][x]-t[z][t[z].length() - 1]<11 or t[z][t[z].length() - 1]  >-11 )
{
cout<<t[z]<<endl;
}
} ```
1
t[z][x] - t[z][t[z].length() - 1]<11

nie ma sensu, bo teraz zawsze porównujesz t[z][x] z ostatnią literką słowa. Chodziło mi raczej o

t[z][x] - t[z][k-1] < 11

Dalej, ta pętla jest niepoprawna, bo nie bierzesz pod uwagę ostatniego elementu ```cpp for(int x=0; x<t[z].length()-1; x++)="x++)" ```="```" warto="warto" trzymać="trzymać" się="się" kanonicznego="kanonicznego" sposobu="sposobu" przechodzenia="przechodzenia" po="po" tablicy,="tablicy," jeśli="jeśli" tablica="tablica" ma="ma" elementów="elementów" to="to" robisz="robisz" ```cpp="```cpp" for="for" (int="(int" i="i" <="&lt;" ++i)="++i)" <br="&lt;br" w="W" c++="C++" `n`="`N`" n;="N;" /> Ale uprośćmy to, po co raz chodzisz do przodu, a raz do tyłu ```cpp for (int x = 0; x < t[z].length(); ++x) for (int k = 0; k < t[z].length(); ++k) ```
0

Możesz to zadanie wykonać w O(N).

0
twonek napisał(a):
t[z][x] - t[z][t[z].length() - 1]<11

nie ma sensu, bo teraz zawsze porównujesz t[z][x] z ostatnią literką słowa. Chodziło mi raczej o

t[z][x] - t[z][k-1] < 11

Dalej, ta pętla jest niepoprawna, bo nie bierzesz pod uwagę ostatniego elementu ```cpp for(int x=0; x<t[z].length()-1; x++)="x++)" ```="```" warto="warto" trzymać="trzymać" się="się" kanonicznego="kanonicznego" sposobu="sposobu" przechodzenia="przechodzenia" po="po" tablicy,="tablicy," jeśli="jeśli" tablica="tablica" ma="ma" elementów="elementów" to="to" robisz="robisz" ```cpp="```cpp" for="for" (int="(int" i="i" <="&lt;" ++i)="++i)" <br="&lt;br" w="W" c++="C++" `n`="`N`" n;="N;" /> Ale uprośćmy to, po co raz chodzisz do przodu, a raz do tyłu ```cpp for (int x = 0; x < t[z].length(); ++x) for (int k = 0; k < t[z].length(); ++k) ```

Zastosowałam się do porad

for (int z=0; z<1000; z++) //przeszukiwanie słów    
{   
for (int x = 0; x < t[z].length(); ++x)
    for (int k = 0; k < t[z].length(); ++k)
if(t[z][x] - t[z][k-1]<11 or t[z][x] - t[z][k-1] >-11 )
{
cout<<t[z]<<endl;
}
} ```
Dalej nie działa. X.x
1

Teraz skoro k ma wartości od 0 do t[z].length() - 1 to warunek powinien być

if(t[z][x] - t[z][k]<11 || t[z][x] - t[z][k] >-11 )
0

Dalej nie działa... robi się coś w rodzaju pętli nieskończonej, ale czy ona jest rzeczywiście nieskończona - nie wiem.

for (int z=0; z<1000; z++) //przeszukiwanie słów    
{   
for (int x = 0; x < t[z].length(); ++x)
for (int k = 0; k < t[z].length(); ++k)
if(t[z][x] - t[z][k]<11 || t[z][x] - t[z][k] >-11 )
{
cout<<t[z]<<endl;
}
}
0

A oczywiście, znaki powinny być w drugą stronę

if (t[z][x] - t[z][k] > 11 || t[z][x] - t[z][k] < -11)
0
twonek napisał(a):

A oczywiście, znaki powinny być w drugą stronę

if (t[z][x] - t[z][k] > 11 || t[z][x] - t[z][k] < -11)

To samo.

1

Ja się na programowaniu nie znam,
Ale mnie się nie podoba ta wartość 11 jako cyfra w warunku. Myślę nad tym od wczoraj i nie rozumiem, skąd komputer ma wiedzieć co to jest 11 jako długość. Jak dla mnie to powinno być wyliczone jako jakaś odległość np:

int odlegosc = t[z][x] - t[z][k] ;

i w warunku

if (odlegosc > 11 || t[z][x] - t[z][k] < -11)

Zresztą czemu nie dać

 abs(t[z][x] - t[z][k])

i warunku po prostu

if (odlegosc > 11)
2

Można też użyć innego algorytmu:

using namespace std;

bool checkWordSort( const string& word , int limit )
{
    set<unsigned char> setwords;

    for( const auto& letter : word )
    {
        setwords.insert( static_cast<unsigned char>(letter) );
        if( abs( *setwords.cbegin() - *(--setwords.cend()) ) > limit ) return true;
    }

    return false;
}

..................

int main()
{
    vector<string> input;

    input.push_back("ABDDEFAAKIO");
    input.push_back("AGHTGGFIIIKIO");
    input.push_back("ABDUUYGGXBVGGASTO");
    input.push_back("CYYTUUIS");
    input.push_back("ABDDEWWEAKIO");
    input.push_back("ABAAO");
    input.push_back("ABUUUZA");
    input.push_back("ABCABC");

    for( const auto& word : input )
    {
       if( checkWordSort(word,11) ) cout << word << "\n";
    }

    return 0;
}
0

Ta "nieskończona pętla" to po prostu wypisywanie tego samego słowa wiele razy, bez spacji ani nowego wiersza między nimi. Główny problem polegał na tym, że jak już wypiszesz jakieś słowo, to powinnaś zakończyć te dwie wewnętrzne pętle. Najłatwiej to zrobić jeśli wrzucisz te wewnętrzne pętle do osobnej funkcji:

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;

void wypisz(const vector<string>& t, int z)
{
    for (int x = 0; x < t[z].length(); ++x)
        for (int k = 0; k < t[z].length(); ++k)
            if (t[z][x] - t[z][k] > 11 || t[z][x] - t[z][k] < -11)
            {
                cout << t[z] << "\n";
                return;
            }
}

int main()
{
    vector<string> t = { "aaabbbccc", "aakddzz", "qqqddhbbb", "eeeeeezzz" };

    for (int z = 0; z < t.size(); z++)
    {
        wypisz(t, z);
    }
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1