Permalänk

Snabb hjälp med C++ uppgift.

Min flickvän har fått en marig c++ uppgift som hon inte lyckats lösa helt och hållet, själv är jag inte så extremt säker på just c++ så jag är verkligen tacksam för all hjälp jag kan få här.

Uppgiften lyder:

Skapa ett program som läser in ett antal heltal (högst 100 stycken) och placerar dem i fält som delas upp i två delar (OBS! Detta sker i ett och samma fält), var sida i fältet skall vara sorterade i storleksordning med minsta talet först.
Om talet som läses in är mindre än 50 skall det placeras i ena fältet och om det är ett tal över 50 läses det in i det andra fältet. Talet 50 läggs in i fältet med de lägre talen. Programmet ska läsa in ett ta i taget och placerar detta i något av fälten.
Inför varje ny inläsning skall de hittills inlästa talen vara sorterade. Sorteringen skall göras med hjälp av bubbelsortering (se uppgifter 18, sida 80 i Skansholm). När användaren avslutar inläggning av tal skall fältets innehåll skrivas ut.

Krav:
Programmet ska
* ha en fungerande inläsning av talet samt en fungerande bubbelsortering
* ha en fungerande utskrift av listan med det minsta talet först för varje del
* sortera fältet i två delar - en med tal över 50 och en med tal under 50
* fälten ska kunna skrivas ut var för sig

Är som sagt väldigt tacksam för all ev. hjälp som kan erbjudas.

Mvh
Lindfors

Permalänk
Medlem

Om hon "inte lyckats lösa [det] helt och hållet" så har hon alltså löst det till stor del. Få se vad hon gjort så kanske vi kan påpeka vad som är fel. Det här låter väldigt mycket som en skoluppgift.

Visa signatur

:€

Permalänk
Hedersmedlem

eighty: Han skrev att det var en uppgift, det tolkar jag som en skoluppgift iaf.

Visa signatur

Vim
Kinesis Classic Contoured (svart), Svorak (A5)
Medlem i signaturgruppen Vimzealoter.

Permalänk
Medlem

Så det är inte exakt uppgiften på s. 80 som skall göras... För den är inte så som du beskriver den.

Men om jag fattat dig rätt så skall ett tal mellan 1-100 sorteras in i en av två listor. Den första listan håller talen mellan 1-50 och den andra håller talen mellan 51 - 100. Talen i de båda listorna skall vara inbördes sorterade och sorteras in så fort de matats in?

Bubblesort är väldigt enkelt. Tala om vad ni inte förstår så skall vi hjälpa er.

Man kan göra så här:
1. Läs in talet
2. Kolla om det är mer eller mindre än 50
3. Placera det sist i rätt av dom två listorna.
4. Kör en bubblesort på den listan.
5. Läs in nästa tal och upprepa proceduren.

Bubblesort:
Vi börjar från vänster i listan och har för avseende att ha det lägsta talet till vänster och det högsta talet till höger i den färdigsorterade listan. Jämför det första paret med tal. Om det första talet är högre än det andra talet i paret så skifta plats på dessa. Nu vet du att dom två talen är inbördes sorterade. Sen tar du och flyttar ett steg och jämför nästa par. Du flyttar bara ett tal. Det högsta talet i den tidigare sorteringen är alltså det vänstra talet i nästa sortering. Nu kollar ni likadant vilket tal som är högst och flyttar plats på talen om det vänstra var högre än det högra. Så tar du nästa par osv... Det som händer är att när du kommer till sista paret av tal så vet du att det högsta talet i det paret är det högsta i hela listan. Det har u flyttats med dit bort. Alltså, ett tal är nu sorterat. Det högsta är längst till höger. Nu är det bara att börja om. På så vis flyttar ni nu upp det näst högsta talet, men ni behöver inte gå hela vägen fram den här gången, för ni vet ju att det högsta talet i listan redan är längst åt höger och att det tal ni det här varvet har "bubblat" fram är det näst högsta i listan. Fortsätt så här tills dess att inget par behöver skiftas i iterationen. Då vet ni att hela listan är sorterad.

Hoppas det hjälpte

/Pelle

EDIT:

Listan från början: 1 4 2 6 7 5 8 9 2 Vi börjar bubbla: (1 4) 2 6 7 5 8 9 3 1 < 4 så ingen förändring 1 (4 2) 6 7 5 8 9 3 4 > 2 så vi skiftar 1 (2 4) 6 7 5 8 9 3 Också tar vi nästa par osv... 1 2 (4 6) 7 5 8 9 3 1 2 4 (6 7) 5 8 9 3 1 2 4 6 (7 5) 8 9 3 -> 1 2 4 6 (5 7) 8 9 3 1 2 4 6 5 (7 8) 9 3 1 2 4 6 5 7 (8 9) 3 1 2 4 6 5 7 8 (9 3) -> 1 2 4 6 5 7 8 (3 9) Detta var en iteration... Nu vet vi att 9:an var det högsta talet och att vi har det längst till höger i listan. Då börjar man om och så kör man så tills inga fler tal behöver skiftas under en hel iteration.

Visa signatur

Man kan inte polera en bajskorv

Permalänk
Medlem

Pelle76: Inte för att vara sån, men ett enterslag i code-blocket hade inte skadat

Permalänk

Bifogar koden hon skrivit. det skumma är att den funkade inte i skolan men hemma. Använder samma kompilator, hursomhelst så skulle jag vara tacksam för lite optimeringsförslag. Måste koden verkligen bli såhär pass lång?

#include "iostream.h" void bubblesort(int *f, int &k); void skriv_ut_lista(int *f, int k); int main(int argc, char* argv[]) { int f[2][100]; int i; int x=0; int y=0; int tal; int antal; int val; cout<<"Hur många tal vill du skriva in(max 100)?"; cin>> antal; for(i=0;i<antal;i++) { cout<<"skriv ett tal"; cin>>tal; if(tal<50) { f[0][x]=tal; bubblesort(&f[0][0],x); x++; } else { f[1][y]=tal; bubblesort(&f[1][0],y); y++; } } cout<<"För att skriva ut listan med tal under 50 tryck 1\n"; cout<<"För att skriva ut listan med tal över 50 tryck 2\n"; cout<<"För att skriva ut båda listorna tryck 3\n"; cin>>val; if (val==1) { skriv_ut_lista(&f[0][0], x); } if (val==2) { skriv_ut_lista(&f[1][0], y); } if (val==3) { cout<<"Lista1:"; skriv_ut_lista(&f[0][0], x); cout<<"Lista2:"; skriv_ut_lista(&f[1][0], y); } return 0; } void skriv_ut_lista(int *f, int k) { for(int i=0;i<k;i++) { cout<<*(f+i); cout<<" "; } } void bubblesort(int *f, int &k) { bool byt_plats = true; while (byt_plats == true) { byt_plats=false; for (int i=0; i<k; i++) { int a=*(f+i); int b=*(f+i+1); if(a>b) { int c = a; a = b; b = c; *(f+i)=a; *(f+i+1)=b; byt_plats = true; } } } }

Permalänk
Medlem

Vad menar du med att det inte funkar? Kompilerar det inte? "iostream.h" finns förmodligen inte. Använd följande istället:

Citat:

#include <iostream>
using namespace std;

Vad menar du med optimering? Om du vill att den ska vara snabbare bör du byta ut bubblesort mot annan sorteringsalgoritm. Eller att göra koden kortare (vilket inte är optimering)? Den var inte särskilt lång...

Visa signatur

:€

Permalänk
Medlem
Citat:

Ursprungligen inskrivet av kj_bassplayer
Bifogar koden hon skrivit. det skumma är att den funkade inte i skolan men hemma. Använder samma kompilator, hursomhelst så skulle jag vara tacksam för lite optimeringsförslag. Måste koden verkligen bli såhär pass lång?

Om du vill ha kortare kod så tycker jag att din bubblesort ser onödigt komplicerad ut.
Jag skulle ha skrivit såhär:

void bubblesort(int *f, int &k) { for (int j=0; j<k; j++) { for (int i=0; i<k-j; i++) { if(f[i]>f[i+1]) { int tmp = f[i]; f[i] = f[i+1]; f[i+1]=tmp; } } } }

Permalänk
Medlem
Citat:

Ursprungligen inskrivet av ptolemy
Om du vill ha kortare kod så tycker jag att din bubblesort ser onödigt komplicerad ut.
Jag skulle ha skrivit såhär:

void bubblesort(int *f, int &k) { for (int j=0; j<k; j++) { for (int i=0; i<k-j; i++) { if(f[i]>f[i+1]) { int tmp = f[i]; f[i] = f[i+1]; f[i+1]=tmp; } } } }

Rätta mig om jag har fel men den där koden sorterar ju även färdigsorterade listor. Bättre att stoppa så fort man har kört en iteration utan att behövt skifta några tal.

Bubblesort kan vara väldigt snabbt om man har att göra med listor som bara är lite osorterade.

I det här fallet skulle jag vilja säga att det är ett aldeles utmärkt sätt att sortera listan på. Man vet ju att listan som man stoppar in det nya talet i alltid är sorterad... Således behöver man bara bubbla igenom listan en gång för att veta att man har sorterat in även det nya talet rätt i listan. Genom att placera det nya talet sist i listan så behöver vi inte ens köra igenom hela listan. Det räcker med att vi kör tills dess vi inte längre behöver skifta två tal.

void sort(int *f, int &k){ bool shifted = true; int i = k; while(shifted && i > 0){ if (f[i-1] > f[i]){ int a = f[i]; f[i] = f[i-1]; f[i-1] = a; } else { shifted = false; } i--; } }

Förutsättningar för att funktionen ovan inte skall balla ur:
1. Den gamla listan måste vara sorterad.
2. Det nya talet skall läggas sist i listan.

EDIT: Ett tag sedan jag sysslade med c++ så kolla om pekarna stämmer i koden ovan. Kan ha smugit sig in lite Java nånstans

EDIT2: Ett gränsvärdesfel i>=0 skulle vara i>0

Visa signatur

Man kan inte polera en bajskorv

Permalänk
Medlem
Citat:

Ursprungligen inskrivet av Pelle76
Rätta mig om jag har fel men den där koden sorterar ju även färdigsorterade listor. Bättre att stoppa så fort man har kört en iteration utan att behövt skifta några tal.

Sant! det var klantigt av mig

Permalänk
Medlem

Jag ser vissa konstigheter i koden.

bubblesort(&f[0][0],x);

&f[0][0] blir i det här fallet en pekare till [0][0]-elementet, inte en pekare till en array, det rätta borde vara bara f[0].

bubblesort(f[0],x);

Sen, vad menas med:

void sort(int *f, int &k)

Det där &-tecknet ska väl inte vara där?

Permalänk
Medlem
Citat:

Ursprungligen inskrivet av Don_Tomaso
Jag ser vissa konstigheter i koden.

bubblesort(&f[0][0],x);

&f[0][0] blir i det här fallet en pekare till [0][0]-elementet, inte en pekare till en array, det rätta borde vara bara f[0].

bubblesort(f[0],x);

Håller med. &f[0][0] är samma sak som &f[0], men det är inte särskilt snyggt.

Citat:

Ursprungligen inskrivet av Don_Tomaso
Sen, vad menas med:

void sort(int *f, int &k)

Det där &-tecknet ska väl inte vara där?

&-tecknet gör så att det blir en referens.

Permalänk
Medlem

Finns dock ingen anledning att det ska va en referens eftersom värdet inte ändras i funktionen.

Permalänk
Medlem
Citat:

Ursprungligen inskrivet av Ereinion
Finns dock ingen anledning att det ska va en referens eftersom värdet inte ändras i funktionen.

Jo, det går snabbare med referens (även om det inte spelar nån roll för uppgiften).
men det är bättre att skriva const int & k i så fall

Permalänk
Medlem

ptolemy:

Att skicka en referens till en int (eller en inbyggd datatyp över huvud taget) som argument vid funktionsanrop är såvitt jag vet ganska meningslöst i C++, om man inte uttryckligen vill att funktionen skall ändra den refererade variabeln. I praktiken blir det ju bara frågan om att maskinkoden gör ett anrop med en 32-bits pekare i stället för en 32-bits heltal (om du kör en 32-bits maskin). Några optimeringsvinster finns då inte att hämta.

Om man inte vill att den anropade funktionen skall ändra den refererade argumentvariabeln är det direkt farligt att skriva funktionen som

int foo(int & bar) { ... }

eftersom man då riskerar att funktionen foo ändrar den refererade variabeln, vilket kan bli svårt att upptäcka senare.

Visa signatur

perga

Permalänk
Medlem
Citat:

Ursprungligen inskrivet av ptolemy
Jo, det går snabbare med referens (även om det inte spelar nån roll för uppgiften).
men det är bättre att skriva const int & k i så fall

Om det hade varit något större, tex en vector hade det gått snabbare. Inte med en int som perga sa.

Permalänk

Har hon ingen lärare? Ja nu fick ni ju kanske ett bra svar här också. Men det är väl det läraren ska göra?

Visa signatur

Python-IRC på svenska: #python.se

Permalänk
Medlem

Kör qsort, mergesort lr likande, (rätt så, kanske kul men det är en annan sak) meningslöst att hålla på att skriva en snabb bubblesort.

(att sortera 7 tal är ju ett trivialt fall, bubble sort är nog snabbare på korta talföljder och en sorterad list vilket också är ett trivialt fall)

#include <stdlib.h>

int tal[] = { 4, 1, 10, 9, 2, 5, 9 };

int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}

int main(void)
{
....
qsort (tal, 7, sizeof(int), compare);
....
}

(bara en parantes

#include "iostream.h"

bör vara

#include <iostream>

using namespace std;

)

Visa signatur
Permalänk
Medlem
Citat:

Ursprungligen inskrivet av perga
Att skicka en referens till en int (eller en inbyggd datatyp över huvud taget) som argument vid funktionsanrop är såvitt jag vet ganska meningslöst i C++, om man inte uttryckligen vill att funktionen skall ändra den refererade variabeln. I praktiken blir det ju bara frågan om att maskinkoden gör ett anrop med en 32-bits pekare i stället för en 32-bits heltal (om du kör en 32-bits maskin). Några optimeringsvinster finns då inte att hämta.

Blir det inte effektivare minnesanvändning med call by reference om man har en rekursiv funktion, eller tänker jag fel?

Permalänk

Var missnöjd med koden så jag skrev helt ny, dessutom kommentarer
Men nu får jag inte koden att funka i mitt borland 5
Vet inte om den kan fungera i någon kompilator, vad kan vara felskrivet?

#include <iostream>
#define NUM 30 // Antalet heltal som ska läsas in
using namespace std;

void bubbleSort(int*); // Deklarerar funktionen bubbleSort, tar emot en int* som skall sorteras.

int main (void)
{
int input[NUM], choice, i; // Input-vektorn är där de inskrivna
talen lagras, choice är användarens val på slutet och i är en räknare.

cout << "Skriv in" << NUM << "antal nummer." << endl; //
Uppmanar användaren att skriva in NUM heltal
for(i = 0;i < NUM;i++)
cin >> input[i];

cout << "Anropar bubbelsortering." << endl;
bubbleSort(input); // anropa bubbleSort();
cout << "Bubbelsortering klar." << endl;

while(true) // Oändlig loop för att användaren ska kunna prova detta underbara program hur många gånger som helst.
{
cout << "Vad vill du göra härnäst?" << endl << "1. Lista nummer under 50." << endl << "2. Lista nummer över 50." << endl << "3.
Sluta." << endl << "?";
cin >> choice;
switch(choice)
{
case 1:
for(i = 0;i < NUM;i++) // Börjar från början och
räknar upp alla tal upp till 50, då hoppar den ur loopen.
{
if(input[i] >= 50)
break;
cout << input[i] << " ";
}
break;
case 2:
for(i = 0;i < NUM;i++) // Börjar från början men
hoppar över alla tal under 50, hoppar ur automatiskt när den är klar.
{
if(input[i] < 50);
else
cout << input[i] << " ";
}
break;
case 3:
return 0;
default:
break;
}
}

return 0;
}

void bubbleSort(int *sort)
{
int i,j,temp; // Två räknare och en temporär variabel för att kunna byta.

for(i = 0;i < NUM;i++) // Går igenom hela vektorn.
{
for(j = 0;j < NUM;j++) // Går igenom hela vektorn en gång för varje element.
{
if(sort[j] > sort[i]) // Om elementet sort[j] är
större än sort[i], byt plats på dem.
{
temp = sort[j];
sort[j] = sort[i];
sort[i] = temp;
}
}
}
}

Permalänk
Medlem

Kompilerar i gcc för mig. Jag får en varning pga multiline string literals. Men strängen kanske blev avklippt i mitten när du postade koden här. Vad får du får kompileringsfel?

Några råd:
Använd const int istället för #define.
Använd int[] istället för int* när funktionen ska ta emot en array.
Deklarera variabler först när de behövs, t ex skriv "for (int i = 0; ...".
Döp variabler till vad de är istället för att kommentera vad de gör när du deklarerar dem.
De flesta av dina kommentarer är helt överflödiga (fast det kanske hjälper när man är nybörjare), t ex "bubbleSort(input); // anropa bubbleSort();"

edit: Det kompilerade alltså efter att jag sett till att enraderskommentarerna inte fortsatte på flera rader. Om du försökte kompilera koden som står där i posten så går det ju naturligtvis inte.

Visa signatur

:€

Permalänk
Hedersmedlem

Kompilerar inte för mig i GCC, f ö bör du använda [code]-taggarna + indentering i koden för att det ska bli lättare att läsa.

Visa signatur

Vim
Kinesis Classic Contoured (svart), Svorak (A5)
Medlem i signaturgruppen Vimzealoter.