Bir grup pozitif tam sayıyla ilgili şunlar biliniyor:
-Sayıların hepsi farklı ve 100’den küçük.
-Tüm sayı çiftlerinin toplamı farklı.
Bu sayıların toplamı en fazla ne olabilir?
Bu probleme çözüm olacak kodu yazmamda yardımcı olurmusunuz?
Sayı çifti derken sıradaki sayı ile bir sonraki sıradaki sayı mı kastediliyor:
Örn:
x = [1, 23, 33, 44, ...]
sayi_cifti1 = [1, 23]
sayi_cifti2 = [33, 44]
yoksa çift basamaklı bir sayının basamaklarındaki sayıların sayı çifti olduğu mu kastediliyor?
x = [23, 33, 44, 45 ...]
sayi_cifti1 = [2, 3]
sayi_cifti2 = [3, 3]
Örneğin liste=[1,2,3,4] bu küme istenen şartı sağlamaz çünkü 1+4=2+3 seçebileceğimiz her ikili toplam farklı olsun diyor soruda
{1,2,3,…98,99} kümesi 99 elemanlı ve çok fazla alt kümesi var (2^99). Bazı alt kümeleri belli bir kurala göre hızlıca elemenin bir yolunu bulmaz isek işlem çok uzun sürer. Zaten gerekli kodun yazılmasından kastınızın olasıkları teker teker deneyecek kodun yazılması olduğunu düşünüyorum.
Cevaba ulaşacak en uygun kodu arıyorum
Aranan kümenin eleman sayısı matematiksel olarak 20den fazla olamıyor zaten böylelikle biraz daha seçenekler azalıyor
Hatta en fazla 19 elemanlı olabilir ama onun da garantisi yok çünkü C(19,2)=190 zaten 1den 99 akadar olan sayıların toplamları 197 farklı değer alabilir dolaysıyla listedeki eleman sayısı 19dan fazla olamaz
Probleme yardımcı olacak biri varmı acaba?
Sadece 19 elemanlı alt kümeleri mi kontrol edeceğiz?
C(99, 19) = 1.0719667408076194e+20 = 132341572939212267400
Bence sayı hala çok büyük. Bu kadar fazla olasılığı kişisel bilgisayarlar ile uygun bir zaman içerisinde kontrol etmek, hele ki Python gibi bir dil ile kontrol etmek günümüzde mümkün değil. İstiyorsanız bu kodun ne kadar sürede çalışacağını deneyin:
for i in range(132341572939212267400): pass
Eğer 19’dan küçük elemanlı kümeleri de kontrol edeceksek sayı daha da büyüyor.
Butun ikili sayi kombinasyonlari kast ediliyor buyuk ihtimalle.
(∀a∀b∀c∀d: a+b = c+d ↔ (a=c ∧ b=d) ∨ (a=d ∧ b=c))
Butun kombinasyonlari uretip bakmak uzun surer ama uretirken optimizasyona gidebiliriz. Mesela {1, 2, 4, 5} ile baslayan C(95, 15) kumenin tamamini atlayabiliriz!
Sorunun hala bu sekliyle zor oldugunu dusunuyorum ama potansiyel cevap uzayi C(99, 19) oldugu icin degil.
Ayni uzayda butun sayilarin ardisik oldugu n<20 kumeler sorulsaydi mesela cok daha kolay olurdu. Oyle degil mi? (Matematigim cok iyi degil, potansiyel cevap uzayinin C(99, 19) + C(99, 18) + … oldugunu cikartmak bile uzun surdu ve siz yazana kadar emin olamadim.)
Problem matematik problemi. Python etiketini cikartabiliriz, o derece.
Subset sum problemi bile NP-complete iken buna nasil pratik bir algoritma bulabiliriz bilemiyorum.
Bizim de böyle işlemlere ihtiyacımız var 
Daha bir de bu şartı kararlaştırdığımız her olasılık için kontrol edeceğiz:
Burada ancak ve ancak kullanmak yanlış olmuş sanki; x∈R , (a=c+x ∧ b=d-x) de olabilir.
O zaman a+b = c+d olmuyor mu? (Yani toplami ayni olan 2 degisik sayi cifti var)
Evet öyle oluyor. …
bazı kısıtlamalara giderek doğru cevaba ulaşmak kolaylaşabiliyor öncelikle istenen kümede 99,98,97,95 olmalı diye düşünürsek
şu yazdığım kod işi rahatlatıyor ama tam sonuçtur diyemesemde sezgisel olarak eminim
import itertools
istenen=[]
a=itertools.combinations(range(50,95),6)
for b in a:
ikilitoplamlist =[197,196,195,194]
arananlar =[99,98,97,95]
for i in b:
içindevarmı = False
geçicitoplamlar = []
for aranan in arananlar:
toplam = i + aranan
geçicitoplamlar.append(toplam)
for ikilitoplam in ikilitoplamlist:
if ikilitoplam in geçicitoplamlar:
içindevarmı = True
break
if içindevarmı == 0:
arananlar.append(i)
ikilitoplamlist.extend(geçicitoplamlar)
istenen.append(arananlar)
for i in istenen:
if sum(i)>826:
print(i)
devamında 50 den küçükleride ekleyeceğiz ama elde edilen listeyi ve ikili toplam listesini yenileyerek
Fotoğrafdaki kodlarınızı kopyalayamayız, kodlarınızı bu linke göre atarsanız bize kolaylık sağlarsınız.
Tamam, yazmak istedigim de oydu zaten: a+b = c+d ise a=c ve b=d, yani ayni toplami veren baska bir cift yok, olmamali.
import itertools
a=itertools.combinations(range(50,95),6)
for b in a:
ikilitoplamlist =[197,196,195,194,193,192]
arananlar =[99, 98, 97,95]
for i in b:
içindevarmı = False
geçicitoplamlar = []
for aranan in arananlar:
toplam = i + aranan
geçicitoplamlar.append(toplam)
for ikilitoplam in ikilitoplamlist:
if ikilitoplam in geçicitoplamlar:
içindevarmı = True
break
if içindevarmı == 0:
arananlar.append(i)
ikilitoplamlist.extend(geçicitoplamlar)
istenen.append(arananlar)
for i in istenen:
if sum(i)>826:
print(i)
1 Beğeni