Witam, tak jak w temacie chce napisac program do ktorego podamy przedzial od tej do tej i program wypisze wszystkie liczby z tego przedzialu w losowej kolejnosci, ale w taki sposob zeby zadna sie nie powtorzyla oraz zeby zadna sasiednia liczba nie roznila sie od niej o jeden.Wiem jak napisac zeby sprawdzalo czy wylosowana liczba nie rozni sie o 1 ale nie mam pomyslu jak sprawdzac czy dana liczba juz nie padla, pomoze ktos ?
Musiałbyś zapisywać sobie te liczby w jakimś zbiorze i sprawdzać czy dana liczba nie padła. Średnia złożoność O(nieskończoność) więc nie polecam ;]
Możesz stworzyć tablicę ze wszystkimi liczbami, pomieszać ją a potem poprzestawiać liczby tak żeby obok siebie nie było tych różniących się o 1.
Możesz też:
- Zrób tablicę wszystkich liczb z twojego przedziału.
- Ustaw modulo = rozmiar_tablicy
W pętli: - Wylosuj sobie za pomocą rand()%modulo indeks z tablicy. tablica[indeks] to twoja wylosowana kolejna liczba
- Jeśli ci nie pasuje bo różni sie od poprzedniej o 1 to przesuwasz sobie ten wylosowany indeks na zasadzie (indeks+i)%modulo i najdalej za 2 razem musisz trafić na pasującą liczbę (o ile nie zostały ci juz tylko 2 liczby :P)
- Zamień ostatnią liczbę z tablicy z tą wylosowaną (tzn przerzuć liczbę z ostatniego indeksu na ten właśnie wylosowany)
- modulo = modulo -1
Minus tego rozwiązania jest taki, że może się okazać że na końcu zostaną ci 2 liczby będące po obu stronach ostatnio wylosowanej (tzn np. wylosowałeś 2 a zostały ci w tablicy 1 i 3)
Nie rozumiem tego twojego algorytmu, zagmatwany troche jest :( Wolalbym jak mowiles na poczatku, pomieszac wszystkie losowo a potem poprzestawiac je tak zeby nie roznily sie o jeden ale jak to zrobic... ?
Algorytm który opisałem jest dość trywialny:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
int main(void) {
srand((time(0)));
int n;
scanf("%d", &n);
int* table = (int*)malloc(n*sizeof(int));
for(int i=0;i<n;i++){
table[i]=i;
}
int modulo = n;
int prevNumber = -1;
int number = -1;
for(int i=0;i<n;i++){
prevNumber = number;
int index = rand()%modulo;
number = table[index];
int retry = 0;
while(abs(number-prevNumber)==1 && retry<3){
index = (index+1)%modulo;
number = table[index];
retry++;
}
table[index] = table[modulo-1];
modulo = modulo-1;
printf("%d ", number);
}
free(table);
return 0;
}
Ale ma wadę o której pisałem -> może sie okazać że na samym końcu dostaniesz dwie liczby które różnią się o 1.
Skąd wziąłeś zadanie? Ono nie ma żadnego rozwiązania, jeżeli y = x + 2.
Shalom, wlasnie wiec skoro ma wade wolalbym to pierwsze rozwiazanie ktore opisales, tylko nie wiem zbytnio jak je wcielic w zycie, pokierowalbys troche
Jak pomieszac tablice ?
Losujesz (w pętli) dwa indeksy w tablicy i przestawiasz wylosowane elementy. Ale takie postępowanie nie prowadzi do celu. Warunek, że różnica dwóch kolejnych liczb jest większa od 1 oznacza, że kolejność nie jest losowa. Jak daleko możesz odejść od losowości? Ja widzę dość prosty algorytm, który wyświetla wpierw (w losowej kolejności) liczby parzyste z przedziału x-y, a potem liczby nieparzyste z tego przedziału.
ale to jest slabe rozwiazanie zadania... http://pl.spoj.com/problems/NIEKOLEJ/ tutaj output jest inny
no okej zrobie wiec tak :) bede wyswietlal w losowej kolejnosci parzyste i nieparzyste
To jest bardzo dobre rozwiązanie, w oryginalnym zadaniu nie ma słowa o losowej kolejności.
//Edit, aż takie proste to to nie jest. Problem może pojawić się na styku: ostatnia parzysta, pierwsza nieparzysta.
Np. n = 5. dla parzystych wylosujesz kolejność 4 0 2
, a dla nieparzystych 1 3 5
. Wtedy musisz cyklicznie przesuwać nieparzyste tak by 5
znalazło się na początku.
Tak, nie ma co sie zbytnio spuszczac, dzieki za za dobre rozwiazanie
A jakby tak wypisać najpierw parzyste od 0 do n, a później nieparzyste od 1 do n?
Tj. dla n = 5 będzie 0 2 4 1 3 5
.
Dla n = 10 0 2 4 6 8 10 1 3 5 7 9
.
bogdans napisał(a):
Np. n = 5. dla parzystych wylosujesz kolejność
4 0 2
, a dla
nieparzystych1 3 5
. Wtedy musisz cyklicznie przesuwać nieparzyste tak
by5
znalazło się na początku.
jak cyklicznie przesuwac ? Nie rozumiem.
Wolalbym tego tak nie wypisywac, wolalbym dodac tam losowosc, i dodam jakis warunek jesli wynik odejmowania bedzie 1 zeby losowalo jeszcze raz
Ale to chcesz wysłać poprawną odpowiedź czy wymyślić jakiś słitaśny algorytmik co będzie się wykonywał kilkukrotnie dłużej?
Some_ONE,
nie chce wysylac, ale chce rozwiazac, moze sie wykonywac dluzej
No to myśl nad innymi sposobami.
mam cos takiego ale naruszenie ochrony pamieci mi wywala ciagle, mysle ze niewiele cos tu trzeba poprawic zeby chodzilo:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int main(void){
srand(time(NULL));
int *tab,n,a,b;
scanf("%i",&n);
for(int i=0;i<n;++i)
tab[i]=i;
for(int i=0;i<n/2;++i){
while(tab[a]%2==0){
a=rand()%n;
}
printf("%i",tab[a]);
++i;
}
for(int i=0;i<n/2;++i){
while(tab[a]%2!=0){
a=rand()%n;
}
printf("%i",tab[a]);
++i;
}
return 0;
}
pewnie wypisuje jakies miejsca spoza tablicy ? potrzebna mi pomoc zeby nie naruszalo ochrony pamieci
@Shalom Zawsze można w tym drugim dać warunek że jeśli takie coś wystąpi to program ma powtórzyć losowanie.
@awuyonk Poczytaj sobie o alokowaniu pamięci i funkcji malloc (albo operatora new w c++)