C dilinde birbirinden farklı random sayılar atama

4 yıl

Er

Konu Sahibi

Arkadaşlar bi ödevim var yardımcı olur musunuz? C'de 20 elemanlı bir diziyi 0-50 arası rastgele sayılardan oluşturmam gerekiyor ama her sayı birbirinden farklı olmalı. sayıları rand ile atıyorum ama en iyi ihtimalle 2 tane sayı birbirinin aynısı çıkıyo nasıl yapabilirim
< Resime gitmek için tıklayın >

C

controller_

4 yıl

Yüzbaşı

0-50 arası çok düşük bir aralık, denk gelmesi normal.

Yapabileceğin şey, rastgele bulduğun sayıyı daha önce oluşturdukların içinde arayıp eğer sayı mevcut ise tekrar sayı oluşturmak olabilir.

H

hynx

4 yıl

Binbaşı

Daha once bulduklarini 50 elemanli dizide tut:
in[sayi]=1 eger sayi onceden bulunduysa
in[sayi]=0 eger sayi onceden bulunmadiysa

Sira sira elemanlari atarken in[sayi]=0 olan bir sayi bulana kadar rand fonksiyonunu calistir.

T

Tuğkan-0153

4 yıl

Yarbay

Bu tür problemler en hızlı Lisp ile çözülür. 5 dakikada yazdığım kod. Bu kodu C'ye dönüştürmek de mümkün (piyasada birçok versiyonu olan Lisp to C compiler ile)

< Resime gitmek için tıklayın >

< Bu ileti mini sürüm kullanılarak atıldı >

S

Stack

4 yıl

Yüzbaşı

3 cevap verilmiş aynı mantıkla. Ancak çözüm üretebilseler dahi doğrusu bu değil!
Çünkü; her seferinde üretilen sayıların aynı sayıya denk gelmesi durumunda, tekrar tekrar rastgele üretilen sayıların sonsuza dek öncekilerle yine aynı gelme olasılığı da var. Bu olmasa bile normalden çok daha uzun sürede hesaplama yapılabilmesi durumu var.

Biraz daha mantıklı düşünüldüğünde doğrusu bulunabilir

Bu mesaja 2 cevap geldi.

G

Gökşen PASLI

4 yıl

Yarbay

Enumerable.Range(1,50).OrderBy(z=>new Random(Guid.NewGuid().GetHashCode()).Next(1,50)).Take(20).ToList().ForEach(z=>Console.WriteLine(z));

C# tarafında böyle olabilir

S

Stack

4 yıl

Yüzbaşı

Sorun anlaşılmadı sanırım. Bahsi geçen çözümlerde "çakışma varsa bir tane daha" mantığı var. Bu bir çözüm olabilir ama kesinlikle verimli değil! Çünkü sonlu değil! Rastgelelikte ne zaman çakışma olup olmayacağı bilinemez. Biraz daha düşünüldüğünde daha doğru ve kesin olan yol bulunacaktır.

H

hynx

4 yıl

Binbaşı

Dogrusu yanlisi diye bir sey yok bu konuda. Bu algoritmalarin genel adi las vegas algorithm'dir (https://en.wikipedia.org/wiki/Las_Vegas_algorithm). Bunlarin iyi yani anlasilmasi ve kodlamasi kolaydir ayni zamanda beklenen calisma suresi genelde diger algoritmalarla yakindir. Tabii gidip permutasyon bulmak icin bu algorithmayi kullanirsan suresi uzun surebilir.

Algoritmanin nasil calisacagina dair matematiksek hesap da yapabiliriz:

Su ana kadar 19 tane sayi bulunmus olsun, 20.sayinin ilk 19 sayidan biriyle ayni olma ihtimali 19/50'dir. 30 kere ust uste onceden bulunmus sayi ile karsilasma ihtimali ise (19/50)30 = 2.5*10^-13, 4000 milyarda bir. Piyango tutturmaktan cok daha az.

Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @Stack

S

Stack

4 yıl

Yüzbaşı

Konu ile alakasız olduğun açık. Kardeşim bu sorunun çözümü bu şekilde değil!!! Geyiği bırak işine bak!
Belli bir noktadan sonra iş illaki karışacaktır. Rastgele sayılar sonsuza dek aynısı da gelebilir. Kaldı ki bir tane değerden bahsetmiyoruz, 20 tane farklı sayı belli bir aralıkta üretilecek.
Bu türden çözümler genel olmalı ve tesadüfe bağlı olmamalıdır. Farzedelim ki 20 değil 20 milyon sayı olacak! Yani çakışmalar olmaması ve işlemin bir an önce bitmesi için çok dua etmek gerekiyor.
Daha mantıklı ve pratik bir yolu var bunun. Biraz saksıyı çalıştırmak gerekli sadece.

Bu mesaja 2 cevap geldi.

Bu mesajda bahsedilenler: @hynx

H

hynx

4 yıl

Binbaşı

Birak sonsuzu 30 tane gelme olasiligi bile 400 milyarda bir. Sorularin birden fazla cozumu olur. Ben kisa ve kutuphane kullanmayan bir cozum sundum en optimize olani degil.

Goksenin de cozumu iyiymis ama sort fonksiyonu gerekiyor.

Ayrica tesadufe bagli olan algoritmalari sevmiyorsan quicksort da kullanilmasin

edit: hesap cok dogru degilmis ama test ettim milyon denemede bir kere bile 30 dan fazla kere ayni sayi cikmadi.



int fe(){
    int ayni= 0;
    int a[20] = {0}, b[50]={0};
    memset(a,0,20*sizeof(int));
    memset(b,0,50*sizeof(int));


    for(int i=0;i<20;i++){
        a[i]=rand()%50;
        while(b[a[i]]){
            a[i]=rand()%50;
            ayni++;
        }
        b[a[i]]=1;
    }
    return ayni;
}


int main(){
    int ct = 0;
    srand(time(NULL));
    for(int i=0;i<1000000;i++){
        if(fe()>30)
            ct++;
    }
    std::cout << ct << '\n';
    return 0;
}

< Bu mesaj bu kişi tarafından değiştirildi hynx -- 27 Mart 2021; 22:44:10 >
Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @Stack

S

Stack

4 yıl

Yüzbaşı

Adam sayıp cevap veriyorum ya neyse. Sen daha neyi kastettiğimi anlamıyor, gereksiz yere bişeyler yazıyorsun. Yani milyondan kastımı bile anlamamışsın! Örneğin milyon aralıktaki değerleri, milyonluk dizilere yerleştirmekten bahsediyorum, sen döngüyle değer üretip başka şeyler üfürüyorsun!

Bilimsel, matematiksel ve istatistiksel olarak bilgisayarlar tarafından rastgele üretilen sayıların ne olacağı asla kestirilemez. Üst üste sonsuz kere bile aynı değer gelmesi imkansıza yakın olsa bile mümkündür. Bunu az biraz ilgili kimseler zaten bilirler.

Özetle; estetik, doğru ve risksiz olan yöntem asla bu değildir. Fazla çakışmanın sana denk gelmemesi başkalarına da gelmeyecek anlamına gelmez. Zaten olayı anlamamışsın bile.

Ayrıca bu kadar "brute force" bir yöntemi savunduğuna göre çaresiz kaldın anlaşılan

Algoritmik anlamda verilecek daha ciddi bir cevabın varsa buyur, yoksa kenara alalım seni.

Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @hynx

H

hynx

4 yıl

Binbaşı

Senin dedigini gayet anladim, benim cozumun milyon sayida yavas calismama ihtimali var? Anlatmaya calistigim sey her zaman en optimize cozume gerek yoktur. Bir soru gorunce aklina gelen mantikli cozumu yazarsin eger yazdigin algoritma yavas calisiyorsa optimize edersin.
En optimize cozumu soruyorsan suan gokseninkinden farkli bir cozum aklima gelmedi gelirse haberdar ederim

Bu mesajda bahsedilenler: @Stack

S

Stack

4 yıl

Yüzbaşı

Bahsedilen çözümlerin optimize edilecek herhangi bir tarafı yoktur. Zaten kullanılan mantık/işlem bellidir. Normal çalışma mantığı kaba kuvvet değer üretme üzerine ve rassaldır. Dediğim gibi eğer daha büyük boyutlu dizlerle çalışılırsa iş çıkmaza girebilir. Küçük bir örnek vereyim;

"1000" farklı/tekil sayıyı "0-1000" aralığında üretmeye çalışalım(0,1,2...999). Eğer aralık çok büyük olursa çakışma ihtimali de o denli az olacaktır. Ancak burada olabilecek en dar kapsamda ele alındı. İşlemin sonuna doğru işler iyice uzayacak ve üretilen rastgele sayının çakışmaması neredeyse imkansıza yakın olacaktır. Kaldı ki milyonlardan bahsetmiyorum bile. Bu yüzden genel ve geçerli bir çözüm değildir.

Doğru çözümü artık belli olmuştur sanırım.

S

SBK

4 yıl

Yüzbaşı

/* Bryan Wilcutt's random scatter algorithm */
/* Generates random-appearing, non-repeating values. */

/* Can be any number within the given range of 32K
Mask must be changed for other ranges. */

#define START_POINT 1

void randScatter()
{
long mask; /* XOR Mask */
unsigned long point;
int val;
unsigned int range = 0x7fff; /* 32K */

mask = 0x6000; /* Range for 32K numbers */

/* Now cycle through all sequence elements. */

point = START_POINT;

do {
val = point % range; /* Get random-appearing value */
printf("%08x\n", val);

/* Compute the next value */

if (point & 1) {
/* Shift if low bit is set. */

point = (point >> 1) ^ mask;
} else {
/* XOR if low bit is not set */

point = (point >> 1);
}
} while (point != START_POINT); /* loop until we've completed cycle */
}

< Bu ileti mobil sürüm kullanılarak atıldı > Bu mesaja 2 cevap geldi.

T

Tuğkan-0153

4 yıl

Yarbay

Benim çözüm rekürsif işlev kullandığı için hesaplama sadece gerektiği kadar uzun sürüyor (rekürsif kodun en büyük avantajıdır) Yukarda yazdığım Lisp kodunu şimdi c++11'e dönüştürdüm:

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
using namespace std;

vector<int> rasgele (int boyut, int cap, int rasg, vector<int> liste ) {
  if (boyut < 1)
    return liste;
  else {
    if (any_of(liste.begin(), liste.end(),[rasg](int elt) {return rasg == elt;}))
      return rasgele(boyut, cap, rand() % cap + 1, liste);
    else {
      liste.push_back(rasg);
      return rasgele(boyut-1, cap, rand() % cap + 1, liste); } } }


int main (int argc, char *argv[]) {
  srand (time(NULL));
  int boyut = atoi(argv[1]);
  int cap = atoi(argv[2]);
  vector<int> gecici{};
  vector<int> listem = rasgele(boyut, cap, (rand() % cap) + 1, gecici);
  cout << "Tekrar etmeyen rasgele " << boyut << " sayi: " ;
  for_each(listem.begin(),listem.end(), [](int n){cout << n << ' ';}); }

Denerseniz oldukça hızlı ve sorunsuz çalıştığını görebilirsiniz.

Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @Stack

S

Stack

4 yıl

Yüzbaşı

quote:

Orijinalden alıntı: SBK

/* Bryan Wilcutt's random scatter algorithm */
/* Generates random-appearing, non-repeating values. */

/* Can be any number within the given range of 32K
Mask must be changed for other ranges. */

#define START_POINT 1

void randScatter()
{
long mask; /* XOR Mask */
unsigned long point;
int val;
unsigned int range = 0x7fff; /* 32K */

mask = 0x6000; /* Range for 32K numbers */

/* Now cycle through all sequence elements. */

point = START_POINT;

do {
val = point % range; /* Get random-appearing value */
printf("%08x\n", val);

/* Compute the next value */

if (point & 1) {
/* Shift if low bit is set. */

point = (point >> 1) ^ mask;
} else {
/* XOR if low bit is not set */

point = (point >> 1);
}
} while (point != START_POINT); /* loop until we've completed cycle */
}

Kodu şöyle güzelce açıkla da ardından olmadık laflar etmesin insanlar olur mu? Hadi bekliyoruz...

Bu mesaja 1 cevap geldi.

S

Stack

4 yıl

Yüzbaşı

quote:

Orijinalden alıntı: Tuğkan-0153

Benim çözüm rekürsif işlev kullandığı için hesaplama sadece gerektiği kadar uzun sürüyor (rekürsif kodun en büyük avantajıdır) Yukarda yazdığım Lisp kodunu şimdi c++11'e dönüştürdüm:

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
using namespace std;

vector<int> rasgele (int boyut, int cap, int rasg, vector<int> liste ) {
  if (boyut < 1)
    return liste;
  else {
    if (any_of(liste.begin(), liste.end(),[rasg](int elt) {return rasg == elt;}))
      return rasgele(boyut, cap, rand() % cap + 1, liste);
    else {
      liste.push_back(rasg);
      return rasgele(boyut-1, cap, rand() % cap + 1, liste); } } }


int main (int argc, char *argv[]) {
  srand (time(NULL));
  int boyut = atoi(argv[1]);
  int cap = atoi(argv[2]);
  vector<int> gecici{};
  vector<int> listem = rasgele(boyut, cap, (rand() % cap) + 1, gecici);
  cout << "Tekrar etmeyen rasgele " << boyut << " sayi: " ;
  for_each(listem.begin(),listem.end(), [](int n){cout << n << ' ';}); }

Denerseniz oldukça hızlı ve sorunsuz çalıştığını görebilirsiniz.

Dostum recursive estetik bir yaklaşım olsa dahi bizler performans söz konusu olduğunda uzak dururuz. Gönderdiğin kodu denedim. 1500 ve sonrasında maalesef çoğu kez crash oluyor. Dediğim gibi aşırı rastlantısal bir yaklaşım bu.

T

Tuğkan-0153

4 yıl

Yarbay

Benim kod, ev ödevi olarak işi görecek yeterlikte. Yine de 1500 adetle yaptığım denemelerde hiç crash olmadı. 1600'e cıktım yine olmadı. 1700'de bazısında crash yapmaya başladı. 5 dakikada yazılmış bir kod olarak gayet iyi yine :)

< Bu ileti mini sürüm kullanılarak atıldı >

Bu mesajda bahsedilenler: @Stack

S

Stack

4 yıl

Yüzbaşı

quote:

Orijinalden alıntı: SBK

/* Bryan Wilcutt's random scatter algorithm */
/* Generates random-appearing, non-repeating values. */

/* Can be any number within the given range of 32K
Mask must be changed for other ranges. */

#define START_POINT 1

void randScatter()
{
long mask; /* XOR Mask */
unsigned long point;
int val;
unsigned int range = 0x7fff; /* 32K */

mask = 0x6000; /* Range for 32K numbers */

/* Now cycle through all sequence elements. */

point = START_POINT;

do {
val = point % range; /* Get random-appearing value */
printf("%08x\n", val);

/* Compute the next value */

if (point & 1) {
/* Shift if low bit is set. */

point = (point >> 1) ^ mask;
} else {
/* XOR if low bit is not set */

point = (point >> 1);
}
} while (point != START_POINT); /* loop until we've completed cycle */
}

Burada geçen şeyin konumuzla ilgisi yok! Basit bitwise işlemlerle her seferinde aynı sonucu döndüren tekil veriler üretiliyor.
Bu açıklamayı senin yapman gerekiyordu ama tahmin de ettiğim üzere olmadı

Ayrıca konu sahibi de ortada yok. Sorup kaybolmuş, o kadar.