5

したがって、プロジェクトオイラーでは、問題4は次のように述べています。

回文数は、両方の方法で同じように読み取られます。2つの2桁の数字の積から作られた最大の回文は9009=9199です。

2つの3桁の数字の積から作られた最大の回文を見つけます。

私は以下を試しました：

    #include <stdio.h>
    #include <stdlib.h>

    int check(int result)
    {
        char b[7];
        sprintf(b, "%d", result);
        if (b[0] == b[5] && b[1] == b[4] && b[2] == b[3])
        {
            return 1;
        }
        else 
        {
            return 0;
        }
    }

    int main () {
        int i;
        int g;
        int final;
        for (i = 999; i > 99; i--)
        {
            for (g = 999; g > 99; g--)
            {
                if (check(g*i) == 1)
                {
                    final = g*i;
                    goto here;
                }
            }
        }
        here:
        printf("%d", final);
}

しかし、これは機能しません。正しい答えの代わりに、私は580085を取得します。これは、少なくとも回文であると思いますが、それでも正しい答えではありません。

私のプログラムを以下から説明しましょうint main：

  1. int iとint gは私の乗数です。それらは2つの3桁の数字です。
  2. int final最大の回文を格納する数です。
  3. すべての数の可能性を取得するために、2つのforループを開始します。
  4. 最初の回文に達したときにgotoを使用してループから抜け出します（おそらくそうすべきではありませんが、このような小さなプログラムにはあまり影響しません）。
  5. 上からカウントダウンしているので、最初の回文は可能な限り最大のものになるはずです。

私のチェックについて説明しましょう：

  1. まず、これらは2つの3桁の数値を掛け合わせて、その値を保持するために文字が必要なサイズを決定するためです。電卓に行って999 * 999を掛けると、6になり、1を足す必要があります。私が以前に投稿した、最後に文字をsprintf置く質問の1つから。\0
  2. さて、charとallができたので、result（i*gにint main）をコピーして、に入れましたchar b[7]。
  3. 次にb、チェックする必要のある各スロットをハードコーディングして、それが自分自身と同じかどうかを確認しました。
  4. それから私はそれに応じて戻りました。1は真、2は偽です。

これは私には完全に論理的に思えますが、奇妙な理由で機能しません。ヒントはありますか？

4

10 に答える 10

13

この仮定は間違っています：

上からカウントダウンしているので、最初の回文は可能な限り最大のものになるはずです。

999*100 = 99900前に確認する998*101 = 100798ので、明らかにそれを当てにすることはできません。

于 2010-07-14T22:16:14.327 に答える
2

問題は、最初に見つけた回文が確かに大きな回文ではないということです。

ほんの一例：

i = 900, g = 850 -> 765000
i = 880, g = 960 -> 844800

最初のものは小さいですが、最初にを繰り返すのでi、次にgそれが最初に発見されます。

わかりました、それらは回文ではありませんが、概念は同じです。

于 2010-07-14T22:20:22.970 に答える
2

あなたはこの問題に正面から取り組んでいると思います。最高から最低までパリンドロームを生成してから、それらを因数分解してチェックする方が効率的です。2つの3桁の要素を持つ最初のものが答えです。

例えば

  bool found = false;
  for (int i = 998; i >= 100; i--)
  {
    char j[7];
    sprintf(j,"%d",i);
    j[3]= j[2];
    j[4]= j[1];
    j[5]= j[0];
    int x =atoi(j);
    int limit = sqrt((float) x);
    for (int z = 999; z >= limit; z--)
    {
      if (x%z==0){
        printf("%d",x);
        found = true;
        break;
      }
    }
    if (found) break;
  }
于 2010-07-14T22:45:20.857 に答える
1

私は上からカウントダウンしているので、最初の回文は可能な限り最大のものでなければなりません

i問題は、大小の回文を見つけた可能性があることですg。次の結果である、より大きな回文がある可能性がありjますk。

i > j and
g < k

（これが理にかなっていることを願っています）。

于 2010-07-14T22:19:12.963 に答える
1

Javaの実装：

public class Palindrome {

    public static void main(String[] args)
     {       int i, j;
            int m = 1;
            int k =11;
            boolean flag = false;

            while (true)
            {;
                if (flag) j = m + 1;
                else j = m;

                for (i = k; i > 0; i--)
                {

                    j++;



                    int number, temp, remainder, sum = 0;
                    number = temp = (1000 - i) * (1000 - j);

                    while (number > 0)
                    {
                        remainder = number % 10;
                        number /= 10;
                        sum = sum * 10 + remainder;
                    }

                    if (sum == temp)
                    {
                        System.out.println("Max value:"+temp);

                        return;
                    }


                }

                if (flag)
                    m++;
             k=k+11;
                flag = !flag;
            }

     }

}
于 2011-02-06T17:53:17.120 に答える
0

パフォーマンスについて一言。非常に単純なネストされたループアプローチを使用しているため、多くの製品を複製する可能性があります。たとえば、999 * 999で始まり、次に999 * 998などです。内側のループが終了すると、外側のループをデクリメントして、999*998と同じ998*999で再開します。

実際に実行したいのは、現在の外部ループ値と同じ値で内部ループを開始することです。これにより、重複する操作が排除されます。このようなもの...

for (i = 999; i > 99; i--)
{
  for (g = i; g > 99; g--)
  {
...

ただし、Emilioが指摘したように、最初に見つけた回文が答えになるというあなたの仮定は正しくありません。明らかに、最初に最大数を計算する必要があります。したがって、これらをこの順序で試す必要があります。999 * 999、999 * 998、998 * 998、999 * 997、998*997など..

テストはしていませんが、次のようなものが必要だと思います（擬似コード）：

x = 999;
n = 0;

while (++n <= x)
{
  j = x;
  k = j - n;

  while (j >= k)
  {
    y = j-- * k;
    if (check(y))
      stop looking
  }
}
于 2010-07-14T22:40:06.623 に答える
0

私はあなたを助けるかもしれないこの記事を見つけました。それはブルートフォースアプローチを改善しました。

于 2012-03-28T18:01:45.907 に答える
0

上記のすべての回答は優れていますが、それでもコードの記述を制限することはできませんでした。@thyrgleによって投稿されたコードは完全です。彼がする必要があるほんのわずかな修正は、どの製品が最大であるかをチェックすることだけです。コードは次のようになります

int i,j,max=0,temp;
for(i=999;i>=100;i--){
    for(j=i;j>=100;j--){
        temp=i*j;
        if(isPalin(temp) && temp>max){
            max=temp;
        }
    }
}
cout<<max<<"\n";
于 2014-10-29T07:46:15.973 に答える
0 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int a[6];

void convertToString(int xy){
    int i,t=100000;
    for(i=0;i<6;i++){
        a[i]=xy/t;
        xy = xy % t;
        t=t/10;
    }
}

int check(){
    int i;
    for(i=0;i<3;i++){
        if(a[i]!=a[6-i]){
            return 0;
        }
    }
    return 1;
}

void main(){
    int x,y,xy,status=0;
    int i=0,j=0,p=0;
    for(x=999;x>99;x--){
        for(y=x;y>99;y--){
            xy=x*y;
            convertToString(xy);
            status = check();
            if(status==1){
                if(xy>p){
                    p=xy;
                    i=x;
                    j=y;
                }
            }
        }
    }

    printf("\nTwo numbers are %d & %d and their product is %d",i,j,p);

}
于 2015-03-26T19:53:07.280 に答える
0 
x,y=999,999

k=0

pal=[]

while (y>99):
    while (x>=100):
        m=x*y
        n=x*y
        while (n!=0):
            k=k*10+(n%10)
            n=int(n/10)
        if(m==k):
            if k not in pal:
                pal.append(k)
        x=x-1
        k=0
    else:
        y,x=y-1,999


pal.sort()
print(pal)

それは最大の回文数として906609を与えます

于 2018-01-13T12:06:22.447 に答える