Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
1
Help us understand the problem. What is going on with this article?
@gushwell

C#で数学パズル - 二乗して回文となる非回文数を求める

More than 3 years have passed since last update.

二乗すると回文数となる数で、二乗する前の数が回文でない正の整数を求めるプログラムを書いてみました。

回文数とは、21512 のように、逆から読んでも同じ数になる数字のことです。

C#のコード

PalindromicSquare.cs
    class Program {
        static void Main(string[] args) {
            using(new Timewatch()) { 
                var solver = new PalindromicSquare();
                foreach (var n in solver.Solve(100000000)) {
                    Console.WriteLine($"{n} * {n} = {(long)n * n}");
                }
            }

        }
    }

    public class PalindromicSquare {
        private bool IsPalindrome(long num) {
            string s = num.ToString();
            int len = s.Length;
            int rx = len - 1;
            int lx = 0;
            while (lx < len / 2)
                if (s[lx++] != s[rx--])
                    return false;
            return true;
        }

        public IEnumerable<int> Solve(int maxnum) {
            for (var i = 1; i <= maxnum; i++) {
                if (IsPalindrome((long)i * i) && !IsPalindrome(i))
                    yield return i;
            }
        }
    }

    public class Timewatch : IDisposable {
        private Stopwatch sw = new Stopwatch();

        public Timewatch() {
            sw.Start();
        }
        public void Dispose() {
            sw.Stop();
            Console.WriteLine($"{sw.ElapsedMilliseconds}ミリ秒 (約{sw.Elapsed.TotalSeconds:#.0}秒)");
        }
    }

PalindromicSquareクラスがその解を求めるクラスで、Solveメソッドは、IEnumerabl<int>を返すメソッドとしています。

少しでも速くなるように、回文かどうかを判定するIsPalindromeでは、文字列を反転させ比較するのではなく、文字列の両端から内側に向かって比較するようにしています。

また、Solveメソッドの中では、IsPalindrome((long)i * i)IsPalindrome(i)よりも先に呼び出すようにしています。

iが非回文である確率よりもi * iが回文となる確率の方が低いはずですから、以下のコードよりもメソッドの呼び出し回数が減り多少速くなります。

      if (!IsPalindrome(i) && IsPalindrome((long)i * i))
          yield return i;

このプログラムでは、100000000以下の値を対象にしました。
手元のPCだと、30秒弱で答えが求まりました。

これよりも大きな値を対象にすると、もっと速度を上げる必要がありますが、処理速度を上げるには根本的にアルゴリズムを考え直す必要がありそうです。
残念ながら、その答えを持ち合わせていません。

Solveメソッドは(IsPalindromeも含めて)、LINQ使えば、もっと簡潔に書けると思います。

なお、このプログラムでは、Timewatchというクラスを定義し、簡単に時間計測ができるようにしています。

結果


26 * 26 = 676
264 * 264 = 69696
307 * 307 = 94249
836 * 836 = 698896
2285 * 2285 = 5221225
2636 * 2636 = 6948496
22865 * 22865 = 522808225
24846 * 24846 = 617323716
30693 * 30693 = 942060249
798644 * 798644 = 637832238736
1042151 * 1042151 = 1086078706801
1109111 * 1109111 = 1230127210321
1270869 * 1270869 = 1615108015161
2012748 * 2012748 = 4051154511504
2294675 * 2294675 = 5265533355625
3069307 * 3069307 = 9420645460249
11129361 * 11129361 = 123862676268321
12028229 * 12028229 = 144678292876441
12866669 * 12866669 = 165551171155561
30001253 * 30001253 = 900075181570009
64030648 * 64030648 = 4099923883299904
11764ミリ秒 (約11.8秒)

この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。

1
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
gushwell
株式会社ジード / Microsoft MVP for Developer Technologies 2005-2020 / 著書『実戦で役立つ C#プログラミングのイディオム/定石&パターン』『新・標準プログラマーズライブラリ なるほどなっとく C#入門』『C#プログラミング入門―オブジェクト指向のプログラミング手法を基礎から解説』

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
1
Help us understand the problem. What is going on with this article?