Forum: Ders Arası RSS
The Algorithm Design Manual, problem 2-50
Ramanujan-Hardy sayıları
acehreli (Moderatör) #1
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: The Algorithm Design Manual, problem 2-50
Ramanujan-Hardy sayıları, iki kübün toplamı olarak birbirlerinden farklı a, b, c, ve d sayıları ile a3 + b3 = c3 + d3 olarak iki farklı biçimde yazılabilen sayılardır. Verilen bir n değerinden küçük a, b, c, ve d değerleri ile yazılabilen bütün Ramanujam [sic] sayılarını bulunuz.

Ali
acehreli (Moderatör) #2
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Hiç akıl kullanmayan aşağıdaki algoritma O(n^2) karmaşıklığında:
import std.stdio;
import std.exception;
import std.format;
import std.algorithm;
 
struct SayıÇifti
{
    int a;
    int b;
 
    void toString(void delegate(const(char)[]) hedef) const
    {
        formattedWrite(hedef, "%s^3 + %s^3", a, b);
    }
}
 
alias SayıÇiftleri = SayıÇifti[];
 
struct RamanujanHardySayısı
{
    int değer;
    SayıÇiftleri çiftler;
 
    void toString(void delegate(const(char)[]) hedef) const
    {
        formattedWrite(hedef, "%s = %-(%s = %)", değer, çiftler);
    }
 
    int opCmp(ref const RamanujanHardySayısı sağdaki) const
    {
        return değer - sağdaki.değer;
    }
}
 
/* Belirtilen değerden küçük bütün sayılarla oluşturulabilen Ramanujan-Hardy
 * sayılarını döndürür. */
RamanujanHardySayısı[] ramanujanHardy(int n)
{
    enforce(n >= 1, "n en az 1 olabilir.");
 
    SayıÇiftleri[int] toplamlar;
 
    foreach (a; 0 .. n - 1) {
        const aKüp = a^^3;
 
        foreach (b; a + 1 .. n) {
            const toplam = aKüp + b^^3;
            toplamlar[toplam] ~= SayıÇifti(a, b);
        }
    }
 
    RamanujanHardySayısı[] sonuç;
 
    foreach (toplam; toplamlar.byKey) {
        auto çiftler = toplamlar[toplam];
        auto adet = çiftler.length;
 
        if (adet > 1) {
            sonuç ~= RamanujanHardySayısı(toplam, çiftler);
        }
    }
 
    return sonuç;
}
 
void main()
{
    auto sayılar = sort(ramanujanHardy(1000));
 
    foreach (sayı; sayılar) {
        writeln(sayı);
    }
}
n==1000 durumunda 3 farklı biçimde yazılabilen sayılar da var:

1729 = 1^3 + 12^3 = 9^3 + 10^3
4104 = 2^3 + 16^3 = 9^3 + 15^3
...
87539319 = 167^3 + 436^3 = 228^3 + 423^3 = 255^3 + 414^3
...

Ne yazık ki işleve 10 bin gibi bir değer verildiğinde bile çözüm çok zaman alıyor. (Sonlanmasını hiç beklemedim. :)) Daha hızlı çözümü var mı?

Ali
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Forum: Ders Arası RSS
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-19, 19:51:28 (UTC -08:00)