Bir sayı N verildiğinde, N iki veya daha fazla ardışık mükemmel karenin toplamı olarak ifade edilebilir mi?

At a recent computer programming competition that I was at, there was a problem where you have to determine if a number N, for 1<=N<=1000, is a palindromic square. A palindromic square is number that can be read the same forwards and backwards and can be expressed as the sum of two or more consecutive perfect squares. For example, 595 is a palindrome and can be expressed as 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2.

Sayının bir palindrom olup olmadığını nasıl belirleyeceğimi anlıyorum, ancak art arda iki veya daha fazla karenin toplamı olarak ifade edilip edilmediğini anlamaya çalışmakta güçlük çekiyorum.

İşte denediğim algoritma:

<div class="snippet" data-lang="js" data-hide="false"> <div class="snippet-code">

public static boolean isSumOfSquares(int num) {
         int sum = 0;
         int lowerBound = 1;

         //largest square root that is less than num
         int upperBound = (int)Math.floor(Math.sqrt(num)); 
         
         while(lowerBound != upperBound) {
             for(int x=lowerBound; x
</div> </div>

Benim yaklaşımım, üst sınırı, sayıya en yakın kareköbe ayarlar ve alt sınırı 1'e ayarlar ve alt sınırdan üst sınıra kadar olan karelerin toplamını değerlendirmeye devam eder. Mesele şu ki, üst sınır aynı kalırken yalnızca alt sınır değişiyor.

3
Sorun ne
katma yazar jwatts1980, kaynak
5 bir olur: 1 ^ 2 + 2 ^ 2, doğru mu? Anladığımdan emin olmak.
katma yazar jwatts1980, kaynak
İlk düşüncem, bir palindromun matematiksel bir kavram olmadığıdır. Bu görsel bir tanesidir. Programlama, bir dize olurdu. Bu nedenle, bir sayının bir palindrom olup olmadığını belirlemek için genel bir algoritma şöyle olacaktır: 1) Onu bir dizgeye dönüştürün, 2) Dize değerini ters dize değeriyle karşılaştırın. (Java'da string.reverse() inanıyorum)
katma yazar jwatts1980, kaynak
@Alundrathedreamwalker anladım, o kısmı kaçırdım.
katma yazar jwatts1980, kaynak
@jwatts NP, bu tür problemleri severim
katma yazar IndieTech Solutions, kaynak
Jwatts'ın sorusu, bir sayının palindrom olup olmadığını kontrol etmeyle ilgili değil. ikinci bölüme ^ 2 dizisini almak istiyor
katma yazar IndieTech Solutions, kaynak
11, palindromdur ancak ardışık bir şekilde ^ 2 olarak ifade edilemez. bu kabul edilebilir mi
katma yazar IndieTech Solutions, kaynak
Bu proje Euler sorunu 125, projecteuler.net/problem=125
katma yazar Paul Hankin, kaynak
Asla y tamsayıları için Math.pow (x, y) kullanmayın, tek yaptığınız zaman kazandırarak kayan nokta hataları satın almaktır. Tekrarlanan kareler veya daha büyük y için ve bunun gibi bir şey için düz x * x yapın.
katma yazar G. Bach, kaynak
USACO sorunu bu mu?
katma yazar lacraig2, kaynak
Lütfen, Döngüden Önce Toplamı 0'a Ayarlayın ve Koşul İçinde Toplamı Kontrol Edin
katma yazar lcastillov, kaynak
Göze çarpan bir hata, döngü boyunca her seferinde toplamı sıfırlamamanızdır.
katma yazar Joshua Byer, kaynak
@ G.Bach Tavsiyeniz için teşekkür ederiz. Bunu daha önce bilmiyordum.
katma yazar Maser, kaynak
@ lacraig2 Hayır, bu bir Üniversite İnterskolastik Birliği (UIL) Bilgisayar Bilimi sorunudur.
katma yazar Maser, kaynak
@JoshuaByer Üzgünüm, rekabet için sahip olduğum algoritmayı yeniden yazmak için acelem vardı ve her tekrarlamadan sonra toplamı 0'a sıfırlamayı tamamen unuttum.
katma yazar Maser, kaynak

10 cevap

Bu, ardışık sayıların karelerinin toplamı olup olmadığını belirlemek için etkili bir algoritma olmalıdır.

  1. Start with a lower bound and upper bound of 1. The current sum of squares is 1.

    public static boolean isSumOfSquares(int num) {
        int sum = 1;
        int lowerBound = 1;
        int upperBound = 1;
    
  2. The maximum possible upper bound is the maximum number whose square is less than or equal to the number to test.

    int max = (int) Math.floor(Math.sqrt(num));
    
  3. While loop. If the sum of squares is too little, then add the next square, incrementing upperBound. If the sum of squares is too high, then subtract the first square, incrementing lowerBound. Exit if the number is found. If it can't be expressed as the sum of squares of consecutive numbers, then eventually upperBound will exceed the max, and false is returned.

    while(sum != num)
    {
         if (sum < num)
         {
             upperBound++;
             sum += upperBound * upperBound;
         }
         else if (sum > num)
         {
             sum -= lowerBound * lowerBound;
             lowerBound++;
         }
         if (upperBound > max)
             return false;
    }
    
    return true;
    

5 , 11 , 13 , 54 , 181 ve 595 . Evet, bazıları palindrom değil, ama sadece ardışık sayılar bölümünün karelerinin toplamını test ediyorum.

1: true
2: false
3: false
4: true
5: true
11: false
13: true
54: true
180: false
181: true
595: true
596: false
2
katma
@RobertDodier Talebiniz yanlış. Test durumlarıma henüz 265 ekledim ve bu true değerini döndürdü. Lütfen toplam 265 'den büyükse kodumun ne yaptığını göz önünde bulundurun - toplamdan çıkartarak lowerBound ' a ilerler. Sonunda 11 ^ 2 + 12 ^ 2 = 265 ulaşacak.
katma yazar rgettman, kaynak
upperBound ve lowerBound 1 olarak ayarlandığında, bu yalnızca bir kareyi temsil eder, 1 ^ 2. 0 sayılır mı? Eğer öyleyse, 0 ^ 2 + 1 ^ 2 sayılır. 2 veya daha fazla ardışık kare olması gerekiyorsa, true değerini döndürmeden önce upperBound öğesinin lowerBound değerinden büyük olduğundan emin olun.
katma yazar rgettman, kaynak
@Downvoter Lütfen bunun nasıl geliştirilebileceğini düşündüğünüzü açıklayın.
katma yazar rgettman, kaynak
Bu doğru değil. Örneğin, 11 ^ 2 + 12 ^ 2 = 265'i bulamaz çünkü 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + 10 ^ 2> 265, yani 11 ve 12 asla dikkate alınmaz.
katma yazar Robert Dodier, kaynak
Algoritmayı yanlış anladım. Düzeltilmiş duruyorum.
katma yazar Robert Dodier, kaynak
Sorun, 0'ın mükemmel bir kare olarak kabul edilip edilmediğini belirtmedi. Bu açıklama gerektiren bir şey. Ancak evet, üst küpün alt küpten büyük olduğundan emin olmak için kontrol etmek gerekir çünkü iki veya daha fazla ardışık kare olması gerekir.
katma yazar Maser, kaynak
Çözümünüz harika bir özlü, ama üst üste 2'ye ayarlanması gerekip gerekmediğini merak ediyorum, çünkü ardışık kareler istiyor ve başlangıçta aynı kare olarak alt küp ve üst küp ayarını yapıyorsunuz. 1 durumunda, çıktı yanlıştır, çünkü 1, iki veya daha fazla ardışık karenin toplamı olarak ifade edilemez (1 ^ 2 + 1 ^ 2 çalışmıyor).
katma yazar Maser, kaynak

Just for play, I created a Javascript function that gets all of the palindromic squares between a min and max value: http://JSfiddle.net/n5uby1wd/2/

HTML

<button text="click me" onclick="findPalindromicSquares()">Click Me</button>
<div id="test"></div>

JS

function isPalindrome(val) {
    return ((val+"") == (val+"").split("").reverse().join(""));
}

function findPalindromicSquares() {
    var max = 1000;
    var min = 1;
    var list = [];
    var done = false, 
        first = true, 
        sum = 0,
        maxsqrt = Math.floor(Math.sqrt(max)),
        sumlist = [];

    for(var i = min; i <= max; i++) {
        if (isPalindrome(i)) {
            done = false;

            //Start walking up the number list
            for (var j = 1; j <= maxsqrt; j++) {
                first = true;
                sum = 0;
                sumlist = [];

                for(var k = j; k <= maxsqrt; k++) {
                    sumlist.push(k);
                    sum = sum + (k * k);

                    if (!first && sum == i) {
                        list.push({"Value":i,"Sums":sumlist});
                        done = true;
                    }
                    else if (!first && sum > i) {
                        break;
                    }

                    first = false;
                    if (done) break;
                }

                if (done) break;
            }
        }
    }

    //write the list
    var HTML = "";
    for(var l = 0; l < list.length; l++) {
        HTML += JSON.stringify(list[l]) + "
"; } document.getElementById("test").innerHTML = HTML; }

Min = 1 ve maks = 1000 olduğunda, döndürür:

{"Value":5,"Sums":[1,2]}
{"Value":55,"Sums":[1,2,3,4,5]}
{"Value":77,"Sums":[4,5,6]}
{"Value":181,"Sums":[9,10]}
{"Value":313,"Sums":[12,13]}
{"Value":434,"Sums":[11,12,13]}
{"Value":505,"Sums":[2,3,4,5,6,7,8,9,10,11]}
{"Value":545,"Sums":[16,17]}
{"Value":595,"Sums":[6,7,8,9,10,11,12]}
{"Value":636,"Sums":[4,5,6,7,8,9,10,11,12]}
{"Value":818,"Sums":[2,3,4,5,6,7,8,9,10,11,12,13]}

Tek tek değerlerin test edilmesini sağlayan güncellenmiş bir sürüm: http://jsfiddle.net/n5uby1wd/3/ Hepsini 1 ila 1.000.000 arasında bulmak sadece birkaç saniye sürdü.

1
katma
@ rgettman biliyorum. Ancak soru, probleme nasıl yaklaşılacağının anlaşılmasıyla ilgili tam bir kodun olmasıydı. Ayrıca çözülmesi eğlenceli bir sorundur ve JSfiddle sonuçları test etmek ve görmek için hızlı ve kolay erişim sağlar.
katma yazar jwatts1980, kaynak
Bu soru java etiketli değil, java olarak etiketlendi.
katma yazar rgettman, kaynak

Perhaps I am missing the point, but considering N, for 1<=N<=1000 the most efficient way would be to solve the problem some way (perhaps brute force) and store the solutions in a switch.

switch(n){
    case 5:
    case 13:
    ...
        return true;
    default:
        return false;
}
1
katma
@JimMischel Rekabetin n aralığı neden bu kadar dar belirttiğini anlamıyorum, ancak yaptılar. Hakimlerin, bazı rakiplere fayda sağlamak için yarışma ortasında kuralları değiştireceğini mi düşünüyorsunuz?
katma yazar emory, kaynak
@JimMischel eğer sınırlı bir aralıktan faydalanırsanız, bana göre kolay bir sorun gibi görünüyor: (int i = 0, i <1000; i ++) {System.out.println ("case" + (i * i + (i + 1) * (i + 1) + ":");} size gerekenden daha büyük (ki sorun değil) daha büyük bir arama tablosu verecektir.
katma yazar emory, kaynak
Sağ. Ve sonra birisi üst sınırı 2 ^ 64 olarak ayarlar ve masayı önceden hesaplamanız bir ömür ve onu depolayabileceğiniz büyük bir disk sürücüsü alır. Ve sorunu gerçekten çözen adam kodunda birkaç parametreyi değiştiriyor ve birkaç dakika içinde çalışıyor ve çalışıyor.
katma yazar Jim Mischel, kaynak
Hayır, bunu yapacaklarından şüpheliyim. Arama tablosunu oluşturma öneriniz, böylece sonuçları hızlı bir şekilde geri gönderebilirsiniz, çünkü arama tablosunu oluşturmak için OP'nin problemini çözmeniz gerekir. Bu yüzden cevabınız, kullanıcının problemini çözmek için problemine olan çözümü kullanmasını söylemektir.
katma yazar Jim Mischel, kaynak
Bu bir cevap değil.
katma yazar Joshua Byer, kaynak

S (n, k) = n ^ 2 + (n + 1) ^ 2 + (n + 2) ^ 2 + ... (n + (k - 1)) ^ 2 belirtilen toplam m, yani, S (n, k) = m. (Palindromları ayrı ayrı test edeceğinizi farz ediyorum.) S (n, k) - m, n. S (n, k) - m için açık bir ifadeyi kolayca çözebilir, ikinci dereceden formülü kullanarak çözebilirsiniz. S (n, k) - m'nin pozitif bir tamsayı kökü varsa, o kökü tutun; bu probleminize bir çözüm sunar.

Bir kareselin pozitif bir tamsayı kökü olup olmadığını kolayca test edebileceğinizi farz ediyorum. Zor kısım muhtemelen, ayırıcının tam sayı kareköküne sahip olup olmadığını belirlemektir; Sanırım bunu çözebilirsin.

You'll have to look for k = 2, 3, 4, .... You can stop when 1 + 4 + 9 + ... + k^2 > m. You can probably work out an explicit expression for that.

1
katma
@EdwardDoolittle S (n, k), n cinsinden kuadratik ve k cinsinden kübiktir. Fakat k verilen, çözmeniz gereken bir değişken değil. Maksimum k'yi bulmak bir kübik çözülmeyi gerektirir, ancak basit bir ikiye ayırma veya hatta doğrusal bir arama yapmayı gerektirir. Bu yüzden bir sorun olduğunu görmüyorum.
katma yazar Robert Dodier, kaynak
Eh, k'nin maksimum değeri 3m küp kök sırasına göredir. M = 595 için, tam olarak 12'dir. Tüm k = 2, 3, 4, ... 12'yi test etmek önemli değildir. M = 10 ^ 6 için maksimum k 144'tür; Yine, tüm değerleri test etmek için büyük bir anlaşma değil. Yeterince büyük bir m için, S (n, k) = m'yi tatmin edecek herhangi bir k bulma yükünün, problemin geri kalanında egemen olacağının farkındayım ve sonra mükemmel kare ayırıcılar bulmak için daha iyi bir yol bulmamız gerekecek. Re: Wolfram Alpha - Bu ifadelerle ne yapmak istediğimi anlamıyorum. Neyse, Maxima ile daha rahatım.
katma yazar Robert Dodier, kaynak
Düzeltme: ilk satırda n kare gerekir. Her durumda, S (n, k) nin n ve k'de kübik olduğuna inanıyorum. İki değişkenli bir kübik Diophantine denklemi elde edersiniz ... çözülmesi kolay değildir.
katma yazar Edward Doolittle, kaynak
Haklısın, n. N için denklemi çözdüğümde, şu ayırıcıyı alıyorum: -3 (k + 1) (k ^ 3 + 3k ^ 2 + 2k-12m) . Mükemmel bir kare olması gerekiyor. Örnek olarak m = 595 alalım. Bunun, k değerlerinin bir demetini test etmeden mükemmel bir kare olmasını nasıl sağlayacağız (muhtemelen sadece seriyi toplamak kadar işe yarar)?
katma yazar Edward Doolittle, kaynak
wolframalpha.com adresine gidin ve bu ifadeyi 1/6 * (n + k) * (n + k + 1) * (2 * (n‌ + k) +1) - 1/6 * (n-1) * (n) * (2 * (n-1) +1) - m
katma yazar Edward Doolittle, kaynak
Buna bir daha baktım ve çözümünüzü sevdim. Önceki yorumumdaki ifade tam olarak S (n, k) -m; Wolfram Alpha n için çözer. Başkalarının ayrıntılarını doldurmak için gönderdim.
katma yazar Edward Doolittle, kaynak
public static boolean validNumber(int num) {
    if (!isPalindrome(num))
        return false;
    int i = 1, j = 2, sum = 1*1 + 2*2;
    while (i < j)
        if (sum >  num) {
            sum = sum - i*i; i = i + 1;
        } else if (sum <  num) {
            j = j + 1; sum = sum + j*j;
        } else {
            return true;
        }
    return false;
}

Ancak sadece on tane "iyi numara" vardır {5, 55, 77, 181, 313, 434, 505, 545, 595, 636, 818}. Ve Bu Çok Yavaş Büyür, N = 10 ^ 6 İçin, Sadece 59 Vardır.

1
katma
public static boolean isSumOfSquares(int num) {
         int sum = 0;
         int lowerBound = 1;

         //largest square root that is less than num
         int upperBound = (int)Math.floor(Math.sqrt(num)); 

         while(lowerBound != upperBound) {
             sum = 0
             for(int x=lowerBound; x
1
katma
Bu Beklendiği gibi Çalışmıyor 595, Döngü Koşulu için toplamı kontrol edin.
katma yazar lcastillov, kaynak
Yanılıyorsun, kodlar arasında dolaş ve tekrar soru sor
katma yazar Joshua Byer, kaynak

İlk mükemmel kareler dizisiyle başlayın, Sayıların 13 ve 17 olduğunu varsayalım, ardından dizinin içereceği: 1, 4, 9 ve 16

Bu tür kontrolleri yapın:


13 eksi 1 (0 ^ 2) 12'dir. 1 mükemmel bir karedir, 12 değildir.

13 eksi 2 (1 ^ 2) 11'dir. 2 mükemmel bir karedir, 11 değildir.

13 eksi 4 (2 ^ 2) 9. 4 mükemmel bir kare, 9 mükemmel bir kare, yani 13 iki mükemmelin toplamıdır

17 eksi 1, 16'dır. 1 ve 16 mükemmel karelerdir . Seçimi ortadan kaldırmak.

İki mükemmel karenin toplamı olmayan bir tane bulana kadar devam et.

0
katma

Bir sayının ardışık kareler toplamı olup olmadığını aşağıdaki şekilde hızlı bir şekilde belirleyip belirleyemeyeceğinizi düşünüyorum, bu yapılması gereken aritmetik miktarını büyük oranda azaltır. İlk olarak, tüm karelerin toplamını önceden hesaplayın ve bunları bir diziye yerleştirin:

0, 0+1=1, 1+4=5, 5+9=14, 14+16=30, 30+25=55, 55+36=91, ...

Şimdi, bir sayı iki veya daha fazla ardışık karenin toplamı ise, yukarıdaki sıradaki başka bir sayıyı elde etmek için yukarıdaki sıradan bir sayı ekleyerek tamamlayabiliriz. Örneğin, 77 = 16 + 25 + 36 ve listelenen numarayı elde etmek için 14 = 0 + 1 + 4 + 9 sayıları ekleyerek tamamlayabiliriz. 91 = 14 + 77 = (0 + 1 + 4 + 9) + (16 + 25 + 36). Konuşmacı, listelenen iki sayının listede en az iki pozisyon olması şartıyla tutulur.

How long does our list have to be? We can stop when we add the first square of n which satisfies (n-1)^2+n^2 > max where max in this case is 1000. Simplifying, we can stop when 2(n-1)^2 > max or n > sqrt(max/2) + 1. So for max=1000, we can stop when n=24.

Kümedeki üyeliği hızlı bir şekilde test etmek için, listedeki numaralara sahip olmamız ve bunları listeye kaydetmemiz gerekir; karma değeri, listedeki sayının konumu olmalıdır, böylece başlangıç ​​noktasından en az iki konum uzakta olup olmadığını belirlemek için konumunu hızlı bir şekilde bulabiliriz.

İşte benim Java önerim:

import java.util.HashMap;

public class SumOfConsecutiveSquares {

 //UPPER_BOUND is the largest N we are testing;
  static final int UPPER_BOUND = 1000;
 //UPPER_BOUND/2, sqrt, then round up, then add 1 give MAX_INDEX
  static final int MAX_INDEX = (int)(Math.sqrt(UPPER_BOUND/2.0)) + 1 + 1;

  static int[] sumsOfSquares = new int[MAX_INDEX+1];
  static HashMap sumsOfSquaresHash
    = new HashMap();

 //pre-compute our list
  static {
    sumsOfSquares[0] = 0;
    sumsOfSquaresHash.put(0,0);
    for (int i = 1; i <= MAX_INDEX; ++i) {
      sumsOfSquares[i] = sumsOfSquares[i-1] + i*i;
      sumsOfSquaresHash.put(sumsOfSquares[i],i);
    }
  }

  public static boolean isSumOfConsecutiveSquares(int N) {
    for (int i=0; i <= MAX_INDEX; ++i) {
      int candidate = sumsOfSquares[i] + N;
      if (sumsOfSquaresHash.containsKey(candidate)
          && sumsOfSquaresHash.get(candidate) - i >= 2) {
        return true;
      }
    }
    return false;
  }

  public static void main(String[] args) {
    for (int i=0; i < 1000; ++i) {
      if (isSumOfConsecutiveSquares(i)) {
        System.out.println(i);
      }
    }
  }

}

İşlevin her çalışması en fazla 25 toplama ve 25 adet hash tablo araması yapar. Çarpma yok.

Sorunu çözmek için etkili bir şekilde kullanmak için, 1, 2 ve 3 basamaklı palindromlar oluşturun (1 basamak kolay: 1, 2, ..., 9; 11: 11, 22, 33 ile çarparak 2 basamak, ..., 99; i * 101 + j * 10. formülüne göre 3 basamaklı Sonra yukarıdaki fonksiyonla palindromları kontrol edin ve doğru döndüğünde yazdırın.

0
katma
  1. yalnızca birkaç tam sayı gücü olduğundan, bir dizi güç oluşturabilirsiniz.
  2. Öyleyse ilk ve son eklenen dizine sahip olabilirsiniz. Başlangıçta ikisi de 1'dir.
  3. toplam, numaranızdan düşükken, en son eklenen dizini arttır Toplamı güncelle
  4. toplamı daha yüksek olsa da, 1'inci endeksi artırın. Toplamı güncelle

Veya herhangi bir dizi olmadan, rgettman'ın cevabında olduğu gibi

0
katma
Bu cevabı seviyorum, çünkü sadece metodun ana hatlarını çiziyor ve anlaşılması daha zor olan kodu atlıyor. Bu, rgettman'ın cevabı ile aynı şekilde yanlış olduğunu söyledi. Örneğin, 11 ^ 2 + 12 ^ 2 = 265'i bulamaz çünkü 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + 10 ^ 2> 265, yani 11 ve 12 asla dikkate alınmaz.
katma yazar Robert Dodier, kaynak
Evet, açıklamadan 4. adımdan sonra 3. adıma geri döndüğünüzü anlamadım.
katma yazar Robert Dodier, kaynak
toplam> 265 olduğunda, 4 puanını alırsınız (sekanstaki 265 ilk karesinden çıkar)
katma yazar StackExploded, kaynak

Bir yöntem (muhtemelen verimli değil) Kafamın üstünden düşünebiliyorum,

Diyelim ki N 90'dır.
X = 9 (90'ın sqrt tamsayısı)

 1. x'den küçük tüm tam sayı güçlerinin bir dizisini oluşturun [1,4,9,16,25,36,49,64,81]  
2. Özyineleme 'yi kullanarak dizideki öğelerin olası tüm kombinasyonlarını oluşturun. [1,4], [1,9], [1,16], .... [4,1], [4,9], .... [1,4,9] .... < br> 3. Her bir kombinasyon için (oluşturduğunuzda) - N toplamına kadar olan toplamın olup olmadığını kontrol edin



**To save memory space, upon generating each instance, you can verify if it sums up to N. If not, discard it and move on to the next.

Örneklerden biri [9,81] olacak, burada 9 + 81 = [90]

0
katma