Üç rakamı 6,920'im var. Verilen bir sayı için, bu üç sayının katları toplamına eşit olup olmadığını kontrol etmem gerekiyor. Ör .: n = 47 için 47 = 9 * 3 + 20Bir sayının diğer sayıların katları olup olmadığını bulmak için Algoritma
n = 23 olduğu belirlenebilir. O (n^3) 'de belirlenebilir. Ama bunu yapmanın daha iyi bir yolu var mı?
Bu bir Doğrusal Diophantin Denklemidir. katsayısı negatif olabilir Eğer
ardından Bézout's identity kontrol edin:toplamı sayıların gcd katları ise, o bir çözüm var.
Örneğinizde gcd = 1, dolayısıyla herhangi bir toplam için bir çözüm var. O yüzden negatif olmayan katsayılarının aradığınız tahmin .. :(
Károly, bir algoritma olarak pro, çözümüme bir göz atabilir misin? – gkovacs90
Ben Senden (sadece katsayıları 0 da olabilir varsa) için bir çözüm var.
6 katları toplamı ve 9 hepsi (3 kendisi hariç) 3'ün katları. Yani biz bir numara 3*k + 20*l eşittir olmadığını kontrol etmek gerekir, söyleyebiliriz.
Yani, bir numara n var ise,
n eğer 3'ün katları, bir ayrışma var ve onu basit bulabiliriz (n çift ise, o tekse n o olacak kadar ilk adıma geçin daha 20 oranında azaltmak 3'ün tam katı değilse, o 9+x*6x*6 olduğunu. 0'ın altına düşerseniz ve hala 3'lük bir katı bulamadıysanız, çözüm yoktur.n > 60için en az bir çözümü vardır.
Neden bu işe yarıyor? Çünkü 20 mod 3 = 2, 40 mod 3 = 1, 60 mod 3 =0. Böylece en fazla 2 kez 20 ile azaldıktan sonra, kolayca çözülebilen 3'lük bir kat bulacaksınız.
Katsayılar negatif olabilir mi? –
grup teorisi ve jeneratörler bakmak gerekir. Tüm para değerleri kümesini kapsayabilmek için gerekli olan minimum madeni para setlerini (pennies, dolar) belirlemek için matematikçiler tarafından çözülmüştür. – lucasg
@KarolyHorvath: n = 41 negatif katsayılarla çözülebilir, bu yüzden sanırım değil. – grc