Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Recomandare bicicleta e-bike 20&#...

Bing-Content removal tool

Nu pot accesa monitorulsv.ro de l...

Cum sa elimini urmele de acnee?
 Wc Geberit

Routere detinute in trecut si in ...

Teii din fața casei

E-Mail in serie prin Excel si Out...
 Modul alimentare rulou/jaluzea ex...

Recuperare fișiere dupa form...

Aplicatii stress test RAM

Asigurare auto hibrid
 Asus B550M - PC-ul nu porneste di...

Tzanca Uraganu - Inconjurat de Fe...

explicatie montaj breadboard

3 Doors Down - Kryptonite
 

random numere

- - - - -
  • Please log in to reply
49 replies to this topic

#37
Africanul

Africanul

    Active Member

  • Grup: Members
  • Posts: 1,739
  • Înscris: 24.10.2003
Vezi edit-ul de la postul unde am bagat cele 20 de generari.
Ce ai bolduit tu era evident, si doar uitandu-te pe cod iti dadeai seama ca exista posibilitatea ca niste elemente sa "ramana pe loc" (sau sa fie aduse la locul lor).
Niciodata n-am afirmat ca algoritmul meu va scoate "permutari perfecte", ci doar permutari! Am respectat definitia permutarii din matematica. Am afirmat ca algoritmul postat de mine returneaza niste rezultate suficient de bune. Nu-i mare branza sa faci un algoritm care sa genereze "permutari perfecte" aleatorii...

Nu exista "permutari perfecte", doar permutari.

Ia un pachet de carti, initial puse in ordine crescatoare, dupa tip (trefla, etc). Amesteca-le jumate de zi. Vei obtine intotdeauna o "permutare perfecta"? Eu n-as baga mana in foc...

Edited by Africanul, 29 September 2005 - 09:58.


#38
sapho

sapho

    Active Member

  • Grup: Members
  • Posts: 1,578
  • Înscris: 22.09.2002
exemplu (cu programul facut de mine :D) :

8 6 7 1 9 3 2 5 0 4
5 1 9 3 0 8 6 4 7 2
1 4 0 6 2 5 9 7 3 8
7 3 5 1 0 8 9 6 4 2
3 8 6 4 1 0 2 9 5 7
0 2 8 5 3 6 4 1 9 7
6 4 9 7 2 8 3 1 0 5
3 9 0 7 4 2 1 8 6 5
0 3 4 9 6 7 2 8 1 5
6 7 3 0 4 1 8 2 9 5
3 1 6 2 8 0 9 4 5 7
9 3 6 2 5 4 0 7 8 1
6 8 7 3 9 5 1 2 0 4
2 1 9 6 7 3 5 8 4 0
9 5 0 7 1 6 8 4 2 3
5 0 3 9 8 1 2 4 7 6
2 3 5 9 0 6 4 1 7 8
9 6 4 1 0 8 7 3 5 2
5 1 7 3 2 4 0 8 6 9
2 5 8 3 1 7 4 9 6 0

cu ocazia astra am descoperit inca o problema la algoritmul tau: (pt n = 10) e foarte greu sa obtii permutari care au mai mult de 2 elemente in comun cu cea initiala.

#39
Africanul

Africanul

    Active Member

  • Grup: Members
  • Posts: 1,739
  • Înscris: 24.10.2003

sapho, on Sep 29 2005, 11:02, said:

cu ocazia astra am descoperit inca o problema la algoritmul tau: (pt n = 10) e foarte greu sa obtii permutari care au mai mult de 2 elemente in comun cu cea initiala.

<{POST_SNAPBACK}>


Posibil! Si care-i problema? "Demonstratia" am facut-o mai sus cu cateva posturi.
Nu a fost vorba niciodata in thread-ul asta sa se genereze "permutari perfecte", doar permutari. Omul ala vroia sa stie cum se "amesteca" o multime...
Iar citatele pe care mi le dai, n-au nici o valoare pentru mine. Serios! Am scos "niste" permutari cu algoritmul meu, intr-un mod foarte simplu si nepretentios.

Ai verificat algoritmul lui Knuth? Poti baga un listing cu 20 de generari?

Edited by Africanul, 29 September 2005 - 10:29.


#40
sapho

sapho

    Active Member

  • Grup: Members
  • Posts: 1,578
  • Înscris: 22.09.2002

Africanul, on Sep 29 2005, 09:53, said:

Nu-i mare branza sa faci un algoritm care sa genereze "permutari perfecte" aleatorii...

<{POST_SNAPBACK}>

ia fa unu-doua, dar nu implementari ale algoritmului lui Knuth, si nici celalalt descris de mine mai sus (ala care porneste de la un singur element, la care tot adaugi cate inca unul, in pozitii aleatoare), sa vedem :D. si sa respecte cerinta aia cu probabilitatea de 1/ N!.

Quote

Nu a fost vorba niciodata in thread-ul asta sa se genereze "permutari perfecte", doar permutari. Omul ala vroia sa stie cum se "amesteca" o multime...
eu ma gandeam ca de vreo 20 posturi (de cand omul a zis ca si-a rezolvat problema) tot despre asta discutam... am si recunoscut la un moment dat, ca pentru ce are el nevoie e suficient algoritmul tau. da cred ca tu ai zis ceva de NASA si cu ce ar fi algoritmii alora mai buni decat al tau :D.

Africanul, on Sep 29 2005, 10:12, said:

Ai verificat algoritmul lui Knuth? Poti baga un listing cu 20 de generari?

<{POST_SNAPBACK}>

pai ti-am zis ca programul meu respeta intocmai algoritmul lui Knuth. numai ca e implementat aiurea (adica prea costisitor din punct de vedere al resurselor) . in rest (pasii si ce se intampla in fiecare pas) sunt exact la fel.

Edited by sapho, 29 September 2005 - 10:38.


#41
Africanul

Africanul

    Active Member

  • Grup: Members
  • Posts: 1,739
  • Înscris: 24.10.2003
:coolspeak:  :coolspeak:  :coolspeak:

Imagineaza-ti ca daca vroiam sa postez un algoritm care genereaza "permutari perfecte", nu veneam cu jucaria pe care am postat-o! Oricine care stie minimul de C si minimul de matematica si-ar fi dat instantaneu seama ca jucaria nu are cum sa scoata la fiecare executie o "permutare perfecta" (doar intamplator!). El asigura in schimb "o permutare corecta" a multimii initiale, doar atat.
Ce m-a "ofticat" a fost ca ai sarit repede cu gura ca "nu e bun": este de-a dreptul infiorator de bun! Tu ai fost cel care ai introdus ideea de "permutare perfecta"...

Oricum, te felicit sincer ca te-ai implicat cu atata ardoare in acest subiect (fara nici un misto!), si ai pastrat un limbaj civilizat (nu ca "altii")... Intr-adevar este bun pentru "exercitiu" din cand in cand sa-ti mai bati capul cu probleme de genul asta. Pacat ca in ceea ce ma priveste, nu prea mai am timp disponibil :crying: Inainte acceptam mai usor "dueluri" de genul asta...

Pace!

Edited by Africanul, 29 September 2005 - 10:55.


#42
sapho

sapho

    Active Member

  • Grup: Members
  • Posts: 1,578
  • Înscris: 22.09.2002
ok. (desi imi pare ca te eschivezi de la a da un algoritm de-asta de permutari perfecte :D).

vezi ca mai dadusem unul (asta citit pe undeva pe net):

sapho, on Sep 29 2005, 00:06, said:

un alt algoritm despre care am citit ar fi ceva de genul: pentru o secventa finita de elemente, se asociaza fiecarui element o valoare generata random. elementele se sorteaza apoi in functie de aceste valori. ideea e sa ai o plaja cat mai mare de numere din care sa alegi valorile astea random, pentru ca valorile generate sa nu se repete (ca sa le poti sorta dupa aia). oricum, banuiesc ca in caz ca se itampla sa se repete, poti vedea asta in rutina de sortare si reiei toata procedura. ideea e sa se intample cat mai rar chestia asta.

<{POST_SNAPBACK}>


putem continua eventual discutia despre faptul ca cei care au implementat STL pt gcc au gresit. m-am uitat si in <algorithm> din implementarea VisualC++, si e tot asa aiurea facuta.

#43
Africanul

Africanul

    Active Member

  • Grup: Members
  • Posts: 1,739
  • Înscris: 24.10.2003

sapho, on Sep 29 2005, 11:54, said:

ok. (desi imi pare ca te eschivezi de la a da un algoritm de-asta de permutari perfecte :D).

vezi ca mai dadusem unul (asta citit pe undeva pe net):
putem continua eventual discutia despre faptul ca cei care au implementat STL pt gcc au gresit. m-am uitat si in <algorithm> din implementarea VisualC++, si e tot asa aiurea facuta.

<{POST_SNAPBACK}>


Nu ma eschivez, serios. Chiar am in cap niste "posibile" solutii (trebuie verificate, iti dai seama). Dar nu prea am timp disponibil sa ma apuc de o chestie de genul asta acum...
Poti s-o consideri eschivare, nu ma deranjeaza!  :peacefingers:
Poate "preia" altcineva continuarea discutiei pe tema asta: este ceva interesant.

Iar despre STL nu stiu o boaba! N-am folosit in viata mea. Stilul meu de programare este unul mai "antic", mai aproape de assembler (de exemplu). Mai masochist! Si intamplator (sau nu) si la firmele unde am lucrat/lucrez tot asa am continuat sa lucrez. Am lucrat si pe PC dar si pe alte deviceuri foarte limitate in resurse, unde a trebuit sa fac tot felul de optimizari de ce vrei tu, iar existenta unui STL ar fi fost mana cereasca! Prefer C-ul batranesc, bun la toate.
Sunt "batran" si inapoiat, stiu.

Edited by Africanul, 29 September 2005 - 11:07.


#44
Riper

Riper

    Active Member

  • Grup: Members
  • Posts: 1,939
  • Înscris: 14.01.2005
mama ce discutie. Dupa parerea mea va certati de pomana. E clar ca algoritmul scris de Africanul e mai rapid cum e clar ca si cel scris de sapho e mai bun. De ce nu incercati sa ajungeti la o intelgere, oricum toata discutia e off topic :)

#45
sapho

sapho

    Active Member

  • Grup: Members
  • Posts: 1,578
  • Înscris: 22.09.2002

Riper, on Sep 29 2005, 11:15, said:

mama ce discutie. Dupa parerea mea va certati de pomana. E clar ca algoritmul scris de Africanul e mai rapid cum e clar ca si cel scris de sapho e mai bun. De ce nu incercati sa ajungeti la o intelgere, oricum toata discutia e off topic :)

<{POST_SNAPBACK}>

la fel cum e clar ca algoritmul lui Knuth e cel mai rapid si cel mai bun :D

iata implementarea lui ca sa fie si mai clar:

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <ctime>

using namespace std;

int main(int argc, char *argv[]) {

    const int sz = 10;             // numarul de elemente
    const int repetari = 10;       // nr de repetari ele generarii
    
    int v[sz];                     // solutia
    int temp1, temp2;              // numere ajutatoare
     
    for (int j = 0; j < repetari; j++) {
        for (int i = 0; i < sz; ++i) v[i] = i; 

        for (int i = 0; i < sz; ++i) { 
            temp2 = i + rand() % (sz - i);   // alegem un element la intamplare din cele ramase
            
            temp1 = v[i];                    // swapping
            v[i] = v[temp2];
            v[temp2] = temp1;
            
            cout << v[i] << "\t";            // afisare
            if ((i + 1) % 10 == 0) cout << endl;
        }
        cout << endl;
    }
    
    system("PAUSE");
    return EXIT_SUCCESS;
}


#46
Africanul

Africanul

    Active Member

  • Grup: Members
  • Posts: 1,739
  • Înscris: 24.10.2003

sapho, on Sep 29 2005, 14:53, said:

la fel cum e clar ca algoritmul lui Knuth e cel mai rapid si cel mai bun :D

iata implementarea lui ca sa fie si mai clar:

<{POST_SNAPBACK}>

N-as fi asa de sigur...
Am copiat EXACT codul de mai sus, asta al lui Knuth, si i-am dat pt. 20 de generari.
Acum, ori Knuth este si el om, ori ai implementat tu gresit algoritmul, ori nu sunt  eu in stare de un copy-paste... Tu l-ai verificat?
Uite ce a iesit:

0 1 2 3 4 5 6 7 8 9 - Multimea initiala

1 9 8 2 0 4 3 7 6 5
5 3 1 9 0 6 2 4 7 8
1 7 8 9 2 0 5 3 4 6
7 1 5 2 0 4 9 8 6 3
3 7 4 5 1 9 2 8 0 6
7 6 8 0 3 9 5 4 1 2
6 3 8 4 1 0 5 9 2 7
6 1 4 5 8 3 2 7 9 0
9 6 1 7 4 5 8 0 3 2
4 0 1 7 9 8 5 3 2 6
3 0 9 2 4 5 7 1 6 8
1 9 6 7 4 0 3 2 5 8
6 7 3 5 9 1 4 8 0 2
0 8 7 6 1 5 9 3 2 4
7 3 1 5 9 4 0 2 6 8
2 8 4 6 7 1 3 9 5 0
0 6 2 9 1 8 3 7 5 4
1 3 8 5 4 6 0 7 2 9    <-- wow, tare Knuth asta...
1 0 7 2 4 8 6 9 3 5
8 0 2 9 3 6 1 4 7 5

Probabil ca mai sunt si alte numere, oricum nu mai conteaza.
Oare difera asta cu ceva fata de al meu?

Edited by Africanul, 29 September 2005 - 14:58.


#47
sapho

sapho

    Active Member

  • Grup: Members
  • Posts: 1,578
  • Înscris: 22.09.2002
din pacate ma pricep prea putin la probabilitati ca sa iti demonstrez ca aparitia unei permutari in care 3 elemente (oarecare) apar pe aceleasi pozitii ca in permutarea initiala, aceasta probabilitate deci este destul de mare. ti-am spus si mai sus ca una din hibele algoritmului tau este ca nu genereaza decat foarte rar astfel de permutari.

sigur pot sa-ti zic numai atat: ca probabilitatea ca un element sa apara pe aceeasi pozitie este de 1/n (adica, de exemplu, din cele n! permutari posibile, primul element apare de (n-1)! pe prima pozitie). ca sa te convingi de chestia asta ruleaza asa:

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <ctime>

using namespace std;

int main(int argc, char *argv[]) {

    const int sz = 10;             // numarul de elemente
    const int repetari = 50000;       // nr de repetari ele generarii
    
    int v[repetari][sz];                     // solutiile
    int temp1, temp2;              // nr ajutatoare
    
    srand (time(0));
     
    for (int j = 0; j < repetari; j++) {
        for (int i = 0; i < sz; ++i) v[j][i] = i; 

        for (int i = 0; i < sz; ++i) { 
            temp2 = i + rand() % (sz - i);   // alegem un element la intamplare din cele ramase
            
            temp1 = v[j][i];                    //swapping
            v[j][i] = v[j][temp2];
            v[j][temp2] = temp1;
            
            //cout << v[j][i] << " ";            // afisare
            //if ((i + 1) % 10 == 0) cout << endl;
        }
        //cout << endl;
    }
    
    
    cout << endl;
    int a[sz];                        // masoara de cate ori un element apare tot pe pozitia sa initiala
    int suma = 0;                 // suma tuturor aparitiilor pe aceeasi pozitie, pentru toate elementele
    for (int i = 0; i < sz; ++i) a[i] = 0;
    for (int j = 0; j < repetari; ++j) {
        for (int i = 0; i < sz; ++i) 
            if (v[j][i] == i) ++a[i];
    }
    for (int i = 0; i < sz; ++i) {
        cout << i << " = " << a[i] << "\n";
        suma += a[i];
    }
    cout << "suma = " << suma << "\n";
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

vei vedea ca algoritmul genereaza, in mare, cam asa ceva (rulare de 50.000 ori):

0 = 5050
1 = 5016
2 = 5032
3 = 4964
4 = 5043
5 = 4988
6 = 5043
7 = 5060
8 = 4998
9 = 4956
suma = 50150

dupa parerea mea, distributia nu e nici asa suficient de uniforma, insa mai mult nu cred ca se poate cere de la functia rand() (ea e de vina, nu algoritmul).

aplicat la algoritmul tau, ca sa vezi cam care e diferenta (tot rulare de 50.000 ori):

cu MAX_SWAP = NR_MAX = 10:
0 = 8683
1 = 8757
2 = 8695
3 = 8669
4 = 8771
5 = 8640
6 = 8770
7 = 8710
8 = 8500
9 = 8643
suma = 86838

cu MAX_SWAP = 2*NR_MAX = 20:
0 = 5278
1 = 5435
2 = 5345
3 = 5239
4 = 5290
5 = 5310
6 = 5368
7 = 5342
8 = 5310
9 = 5349
suma = 53266

cu MAX_SWAP = 3*NR_MAX = 30:
0 = 5160
1 = 4948
2 = 4958
3 = 4903
4 = 5066
5 = 5039
6 = 5058
7 = 4993
8 = 5087
9 = 5025
suma = 50237

dupa cum vezi, cand NR_MAX = 10 si MAX_SWAP = 30, algoritmul tau se apropie de ceea ce ar trebui sa fie. la numar mai mare de elemente, trebuie sa ai MAX_SWAP si mai mare.

#48
Africanul

Africanul

    Active Member

  • Grup: Members
  • Posts: 1,739
  • Înscris: 24.10.2003
Da, probabil ca ai dreptate, nu stau sa verific. Algoritmul care l-am dat eu este o jucarie, nu-ti bate capul cu el!
Oricum, nu uita ca functia rand() este limitata pe intervalul [0..n) (chestia cu %), ea returneaza numere "suficient de aleatorii" pe un interval "suficient de mare", doar ca este gatuita de acel modulo, iar pe un interval mic (cum era asta 0..9) incepe sa se simta "gatuirea"...

#49
sapho

sapho

    Active Member

  • Grup: Members
  • Posts: 1,578
  • Înscris: 22.09.2002
mi-am modificat programul ca sa masoare de cate ori apare o permutare in care k numere se gasesc pe pozitiile lor initiale. outputul se citeste cam asa:
0 (nici un element nu se regaseste pe pozitia sa initiala) = nr de astfel de permutari
1 (un singur element pe pozitia sa) = ......
10 (toate elementele se gasesc pe pozitiile initiale - permutarea identica cred ca se numea in matematica)

rezultatul (rulare de 10.000 ori):
b[0] = 3705
b[1] = 3724
b[2] = 1802
b[3] = 574
b[4] = 161
b[5] = 30
b[6] = 4
b[7] = 0
b[8] = 0
b[9] = 0
b[10] = 0

concluzii:
1. numarul de permutari in care niciunul din numere nu e pe pozita initiala am impresia ca e egal cu, sau mai mic decat numarul de permutari in care se "repeta" un singur element.

2. numarul de permutari cu 3 "repetari" reprezinta cam 6% din numarul total de permutari. deci din cele 20 de permutari (cat avea listingul tau) e foarte probabil una sa fie de acest tip.

Edited by sapho, 29 September 2005 - 18:50.


#50
mosu16

mosu16

    Junior Member

  • Grup: Members
  • Posts: 76
  • Înscris: 10.04.2006
am si eu o problema..iar  :P
vreau sa fac un program in care eu sa introduc niste nume(in textbox) si care sa imi repartizeze pe acestia in mai multe grupe
Si sa arate asa
Nume1 =TEXTBOX -------------Grupa A, TEXTBOX(in text box sa-mi afiseze 4 nume la nimereala diferite)
Nume2 =Textbox --------------Grupa B, TextBOX(4 nume din cele ramase,diferite)
...  ------------------------------- Grupa C-etc
Nume16=TEXTBOX -------------Grupa D-etc

si altul Care din 16 ekipe participante sa aleaga una pt fiecare grupa
ekipa1=(TEXTBOX ----------------Grupa A, TextBOX(Una din cele 16 ekipe)
ekipa2= TExtBox  ----------------- Grupa B, TExtBox(una din cele 15 ramase)
...  ----------------------------------- Grupa C,TextBox(una din 14 ramase)
ekipa16=TExtBox -------------------Grupa D, TextBox(una din cele 13)-si restul sa ramana neafisate
Ma poate ajuta cineva? :worthy:

Edited by mosu16, 14 April 2006 - 16:03.


Anunturi

Chirurgia endoscopică a hipofizei Chirurgia endoscopică a hipofizei

"Standardul de aur" în chirurgia hipofizară îl reprezintă endoscopia transnazală transsfenoidală.

Echipa NeuroHope este antrenată în unul din cele mai mari centre de chirurgie a hipofizei din Europa, Spitalul Foch din Paris, centrul în care a fost introdus pentru prima dată endoscopul în chirurgia transnazală a hipofizei, de către neurochirurgul francez Guiot. Pe lângă tumorile cu origine hipofizară, prin tehnicile endoscopice transnazale pot fi abordate numeroase alte patologii neurochirurgicale.

www.neurohope.ro

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate