Algorytm "Flaga polska" sortowanie 01
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

Algorytm "Flaga polska" sortowanie 01

AutorWiadomość
Temat założony przez niniejszego użytkownika
Algorytm "Flaga polska" sortowanie 01
» 2018-06-05 12:51:28
Witajcie

Mam takie oto zadanie

Napisać program, w którym od użytkownika zostaną pobrane dane o wynikach z egzaminu dla n studentów.

- nr indeksu
- ocena

Należy wymusić podanie poprawnych danych.

Program ma podzielić studentów na dwie grupy - zdane / nie zdane. (Wszystko ma się dziać w tabeli wejściowej)

Program ma wyświetlać informację ilu studentów otrzymało maksymalną ocenę (nie musi być to 5) oraz numery ich indeksów.

W programie zaimplementować minimum 4 funkcje

1) pobranie danych
2) algorytm sortowania
3) wyświetlanie danych
4) wyznaczenie studentów z najwyższą oceną

WARUNEK KONIECZNY że algorytm sortowania ma mieć złożoność przeciętną / wagę A(n) = W(n) = n

Mam taki kod (oczywiście nadal z błędami, których już nie umiem wyplenić sama).

Bardzo proszę o pomoc


C/C++
#include <iostream>

using namespace std;

struct students {
    int nrind;
    float score;
};

// data
void data( int nrind, float score ) {
    cout << "Data for how many students do you want to sort?" << endl;
    int n;
    cin >> n;
    students people[ n ];
   
    cout << "Now please pass the index number and a score for everyone." << endl;
    cout << "Your index number must contain only 5 numbers" << endl;
    cout << "Possible scores are 2 , 3 , 3.5 , 4 , 4.5 , 5" << endl;
   
    for( int i = 1; i < n; i++ )
    {
        cout << "Index number" << endl;
        cin >> people[ i ].nrind;
        if( !cin )
        {
            cout << "Pass the correct index number" << endl;
            cin.clear();
            cin.sync();
            // POWRÓT DO CIN ZCZYTUJĄCEGO NR INDEKSU
        }
        else
             cout << "Score for student " << people[ i ].nrind << endl;
       
        cin >> people[ i ].score;
        if( people[ i ].score != 2 && people[ i ].score != 3 && people[ i ].score != 3.5 && people[ i ].score != 4 && people[ i ].score != 4.5 && people[ i ].score != 5 )
        {
            cout << "You've passed a wrong score! Your score must be one of 2 , 3 , 3.5 , 4 , 4.5 , 5" << endl;
        }
        // POWRÓT DO CIN ZCZYTUJĄCEGO OCENĘ
    }
}
void sort01( int nrind, float score, int n, struct students people[] )
{
   
    for( int i = 1; i < n; i++ )
    {
        for( int j = n; j <= i; j-- )
        {
            if( people[ i ].score > people[ n ].score )
            {
                swap( people[ i ].score, people[ n ].score );
            }
        }
    }
}

void show_data( int nrind, float score, int n, struct students people[] )
{
    for( int i = 0; i < n; i++ )
    {
        cout << people->nrind[ i ] << " " << people->score[ i ] << endl;
    }
}

void highest_score( int nrind, float score, int n, struct students people )
{
    float max = people.score[ 0 ];
    cout << "Highest scores were " << endl;
    int how_many = 0;
    for( int i = 1; i < n; i++ )
    {
       
        if( people.score[ i ] >= max )
        {
            max = people.score[ i ];
            cout << people.nrind[ i ] << " " << people.score[ i ] << endl;
            how_many++;
           
        }
       
    }
    cout << how_many << " students got the highest score" << endl;
}

int main()
{
   
    int nrind, score, n;
    char choice;
    cout << "Welcome to the sorting program!" << endl;
   
    cout << "Can we start? Press [Y] for yes or [N] for no." << endl;
    cin >> choice;
   
    if( choice == 'Y' )
    {
        data( nrind, score );
        sort01( nrind, score, n, students people ); //JAK PRZEKAZAĆ STRUKTURĘ??
        show_data( nrind, score, n )
        highest_score( nrind, score, n )
    }
    else
    if( choice == 'N' )
    {
        cout << "See you next time!" << endl;
    }
    else
         cout << "Wrong character. Pick [Y] for yes or [N] for no" << endl;
   
    return 0;
}

W odpowiednich miejscach są komentarze, ale :

1. Jak poradzić sobie z powrotem do początku wczytywania danych od użytkownika jeśli program wykryje błędnie podane dane? (Mamy nie używać goto)
2. Po wyświetleniu informacji o źle wybranym znaku (ani Y ani N) chciałabym, żeby wracało ponownie do pytania co wybiera użytkownik. Próbowałam przez do while ale powiela mi później bez sensu linie :/
3. Dostaje błędy :
                                  linia 100 wywołanie funkcji sort01 (nie wiem jak przekazać tam strukturę, tak samo z pozostałymi wywołaniami funkcji)
                                  invalid types float[int] oraz int[int] for array subscript (63,69,75,itd)
4. Nie jestem pewna sortowania. Ma to być algorytm "flaga polska". Mam schemat NS jednak nie wiem czy poprawnie obudowałam go kodem c++.

Proszę o pomoc
P-171388
» 2018-06-05 14:29:33
students people[ n ];
VLA w C++ nie działa. Użyj
std::vector
.

C/C++
if( people[ i ].score != 2 && people[ i ].score != 3 && people[ i ].score != 3.5 && people[ i ].score != 4 && people[ i ].score != 4.5 && people[ i ].score != 5 )
To nie musi zadziałać. Porównania na liczbach zmiennoprzecinkowych należy wykonywać uwzględniając epsilon.

Jak poradzić sobie z powrotem do początku wczytywania danych od użytkownika jeśli program wykryje błędnie podane dane?
Użyj dowolnej pętli, na przykład:
C/C++
do
{
    //wczytaj dane
} while( niepoprawne );

Próbowałam przez do while ale powiela mi później bez sensu linie
Bez kodu można tylko zgadywać, dlaczego to nie działało.

jak przekazać tam strukturę
Najprostszy sposób to przekazywanie przez wartość, czyli tak samo, jak każdą inną zmienną. Wstawiasz typ i nazwę na liście argumentów, a przy wywołaniu podajesz tylko nazwę zmiennej.

C/C++
for( int i = 1; i < n; i++ )
{
    for( int j = n; j <= i; j-- )
    {
        if( people[ i ].score > people[ n ].score )
        {
            swap( people[ i ].score, people[ n ].score );
        }
    }
}

int i = 1;
int j = n;
Tablice indeksujemy od zera.

j <= i;
Na pewno taki ma być warunek pętli?

algorytm sortowania ma mieć złożoność przeciętną / wagę A(n) = W(n) = n
Co do implementacji, to na razie wygląda mi to bardziej na jakieś sortowanie bąbelkowe o złożoności kwadratowej, czyli raczej źle.
P-171389
Temat założony przez niniejszego użytkownika
» 2018-06-05 15:04:55
Schemat NS do algorytmu wygląda tak

Sort01(n,a)
L:=1; p:=n;
p>l
    (a[l]="0") i (l<p)
          l:=l+1
    (a[p]="1") i (l<p)
          p:=p-1
    (a[l]:=a[p])
     l:=l+1, p:=p-1


Co do struktury - nie mogę jej użyć w C++? Jej użycie było narzucone na lekcji.
P-171390
» 2018-06-05 17:27:54
Co do struktury - nie mogę jej użyć w C++?
Możesz używać struktur. Nie możesz jedynie robić tablicy w ten sposób. Dotyczy to wszelkich tego typu tablic,
int tablica[ n ];
 też byłoby błędne, ponieważ rozmiar tak tworzonych tablic musi być stałą czasu kompilacji. Zamiast tego użyj
std::vector < typDanych > zmienna;
, użycie jest bardzo podobne do zwykłych tablic (jest jeszcze dynamiczne przydzielanie pamięci za pomocą
new
, ale jeśli w materiałach nie masz nic na ten temat, to już lepiej użyć wektora).

L:=1; p:=n;
W matematyce indeksowanie może zaczynać się od jedynki (i zwykle tak właśnie jest). W C++ tablice są indeksowane od zera, więc trzeba wszystkie indeksy odpowiednio poprzestawiać.

p>l
    (a[l]="0") i (l<p)
          l:=l+1
    (a[p]="1") i (l<p)
          p:=p-1
    (a[l]:=a[p])
     l:=l+1, p:=p-1
No właśnie. Zamiast kombinować z dwiema pętlami, to po prostu przetłumacz to na C++. Wynik końcowy będzie bardzo podobny. Na początku masz warunek kończący pętlę, później przy "wyrażenie1 i wyrażenie2" masz zwykłe
if
, natomiast := to nic innego, jak przypisanie za pomocą
=
 (nie mylić z porównaniem przez
==
).
P-171393
Temat założony przez niniejszego użytkownika
» 2018-06-05 20:20:33
:/ właśnie przeniesienie tego na c++ to mój problem
P-171398
» 2018-06-05 21:40:43
Na czym konkretnie polega ten problem? Czytasz wyrażenie matematyczne i zapisujesz kod w C++. Jeśli rozumiesz ten zapis w postaci matematycznej i umiesz wykonać ten algorytm ręcznie na kartce papieru, to nie rozumiem, co stoi na przeszkodzie, aby to zapisać w C++. Na początek:
Zapis matematycznyC++
:=
=
>
>
=
==
i
&&
tablica[indeks]
tablica[ indeks - 1 ]
Mając podany zapis matematyczny wystarczy tylko zmienić oznaczenia i już masz większość kodu bez jakiegoś specjalnego wysiłku. Do tego dojdzie jakaś pętla, na przykład
while
, dojdzie instrukcja
if
 (wcięcia w zapisie matematycznym dość wyraźnie sugerują, gdzie to umieścić, zwłaszcza jeśli rozumiesz sam algorytm) i w zasadzie to już chyba wszystko. Doprecyzuj, na którym etapie się zatrzymujesz, bo naprawdę kończą mi się pomysły, jak to jeszcze bardziej łopatologicznie wyjaśnić bez podawania gotowca.
P-171404
Temat założony przez niniejszego użytkownika
» 2018-06-06 13:56:52
int sort01 (int n, struct students people[])
{

int l=0;
int r=n-1;

    while (l<r)
    {
        if (people[l].score == 2)
            {
            l++;
            }
        else if (people[r].score > 2)
        {
            r--;
        }
        else

            struct students temp = people[l];
            people[l] = people[r];
            people[r] = temp;

    }

}

Zmieniłam na taką postać + zmiany w kodzie, ale krzyczy, że temp nie zostało 1) wykorzystane, 2) zadeklarowane
P-171416
» 2018-06-06 14:21:21
Wywal słowo
struct
. To jest typ taki, jak każdy inny,
struct
 występuje tylko przy tworzeniu nowego typu, wszędzie indziej wpisujesz
typ zmienna
.
P-171417
« 1 » 2
 Strona 1 z 2Następna strona