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 >

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

SBK

4 yıl

Yüzbaşı

quote:

Orijinalden alıntı: Stack

Allah razı olsun senden çok istifade ettik

İşte bu yüzden Türkçe forumlarda teknik konu başlıklarına yazmaktan çok önceleri vazgeçmiştim.

Stackovrrflow'da, go4expert'te, hackerrank'te böyle Ortadoğu kafalı biri çıkıp sululuk yapınca, özellikle de rookie seviyede biriyse anında tekmeyi basıyorlar.

Haydi selam ve dua ile

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

S

SBK

4 yıl

Yüzbaşı

quote:

Orijinalden alıntı: controller_

@SBK ben seni ta 2005 den buranın Elektronik forumundan hatırlıyorum. Elektronik forumu artık beyaz eşya tamirine döndüğü için bende buraya geldim
Burada da ergenden geçilmiyor DH nin eski elektronik forumu çok sağlamdı. Benim hatırladığım ChipArchitect vardı yine VLSI tasarımında çalaışan. BlueICE vardı, i368 vardı. Hey gidi günler

O zamanlardan tanisip güzel dostluklar kurduğum kişiler oldu. Birisi şu anda AMD/Austin'de GPU mimarileri.uzeirne çalışıyor, biri de Intel/Varsova'da low level network protokolleri ile ugrasiyor.
Forum cidden guzeldi. Su anda bu.sekilde duzgun insanlarla tanisilabilecek bir ortam bilmiyorum. Retro bilgisayar forumlarinda (forum ismi vermeyeyim) gayet saglam karakterli arkadaslar var. Sanirim yasla da ilgili bu. Bu cihazlara ilgi duyan insanlar 40+ genelde.

< Bu mesaj bu kişi tarafından değiştirildi SBK -- 2 Nisan 2021; 0:34:10 >

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

S

SBK

4 yıl

Yüzbaşı

quote:

Orijinalden alıntı: hynx

Hala bu konuda tartışma dönüyor. Sonunda çözümünü yazmışsın, bu çözüm ne zaman yavaş çalışıyor sana açıklayayım

Soruda verilen sayılara N=50, K=20 diyelim. List uzerinde pop işleminin average time complexitysi O(N) dir. Dediğin çözüm O(N*K) olacak. N sayısını artırınca bu çözüm yavaş çalışır. Buna karşılık N=1e6 iken basit bir hashmap kullanırsan milyon kat daha hızlı çalışan bir sonuç elde edebilirsin çünkü N sayısının bir etkisi olmaz. Bu yüzden sana soruya göre çözüm yazılır dedim.

hashmap, O() notasyonunda rahatlatıcı gözükse da hashmap hesaplaması, instruction cycle olarak biraz maliyetli bir iş. lose lose, sdbm gibi hash fonksiyonların implementation'larında hep rahatsız edici bir while() loop vardır :)

S

scientia

4 yıl

Binbaşı

Birinci sınıf BM öğrencisiyim ve konuyu şöyle okudum:

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

----

Hocamız yüksek performanslı algoritma geliştirmenin herkesi harcı olmadığını ve çok nadir bulunduğunu söyledi. Bulanlar da isim alıp markalaşıyormuş. Bizim yapacağımız sıfırdan yüksek performanslı algoritma geliştirmek yerine best practices dedikleri yöntemleri araştırıp mantığını anlayıp uygulamak. Bu problem özelinde şöyle ilerlememiz gerekmez miydi?

[1]: Problemi anla.
[2]: Best practices araştırması yap.
[3]: Probleme uygulama.
[4]: Test et.

Hocamız yanılıyor bu noktada?

Yine derste sürekli algoritma analizi yapıyoruz. Aynı bu tür sorular soruluyor ve ilk biz aklımıza gelen yöntemi söylüyoruz. Hoca hiç eleştiri yapmadan onu yazıyor. Sonra sürekli onun üzerinden iyileştirme yapmaya çalışıyoruz. Stack hocanın sanırım vurgulamak istediği buydu. Performans odaklı olması lazım çözümlerin.

< Bu mesaj bu kişi tarafından değiştirildi scientia -- 3 Nisan 2021; 16:58:18 >

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.

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.