VBScript で Project Euler Problem 4 - ONLY DO WHAT ONLY YOU CAN DO

左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.

では, 3桁の数の積で表される回文数のうち最大のものを求めよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%204

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

http://projecteuler.net/problem=4

「3桁の数の積」ということだが、999 から 100 まで計算する必要もないだろうと...

Option Explicit
 
Private cnt: cnt = 0
Private max: max = 0
 
Call main
 
WScript.Echo "CNT = " & cnt
WScript.Echo "MAX = " & max
 
Private Sub main()
    Dim i
    For i = 999 To 900 Step -1
        Dim j
        For j = 999 To 900 Step -1
            cnt = cnt + 1
 
            Dim n: n = i * j
            Dim s: s = CStr(n)
            If s = StrReverse(s) Then
                If max < n Then
                    WScript.Echo CStr(i) & " * " & CStr(j) & " = " & s
                    max = n
                End If
            End If
        Next
    Next
End Sub

D:\Project Euler\Problem 004>cscript //nologo 001.vbs
993 * 913 = 906609
CNT = 10000
MAX = 906609

993 * 913 と、913 * 993 の２回計算してしまうので、同じ数の組み合わせを省略

Option Explicit
 
Private cnt: cnt = 0
Private max: max = 0
 
Call main
 
WScript.Echo "CNT = " & cnt
WScript.Echo "MAX = " & max
 
Private Sub main()
    Dim i
    For i = 999 To 900 Step -1
        Dim j
        For j = i To 900 Step -1
            cnt = cnt + 1
 
            Dim n: n = i * j
            Dim s: s = CStr(n)
            If s = StrReverse(s) Then
                If max < n Then
                    WScript.Echo CStr(i) & " * " & CStr(j) & " = " & s
                    max = n
                End If
            End If
        Next
    Next
End Sub

D:\Project Euler\Problem 004>cscript //nologo 002.vbs
993 * 913 = 906609
CNT = 5050
MAX = 906609

最大値以下なら、回文数かどうかのチェックは不要

Option Explicit
 
Private cnt: cnt = 0
Private max: max = 0
 
Call main
 
WScript.Echo "CNT = " & cnt
WScript.Echo "MAX = " & max
 
Private Sub main()
    Dim i
    For i = 999 To 900 Step -1
        Dim j
        For j = i To 900 Step -1
            Dim n: n = i * j
            If n < max Then Exit For
             
            cnt = cnt + 1

            Dim s: s = CStr(n)
            If s = StrReverse(s) Then
                If max < n Then
                    WScript.Echo CStr(i) & " * " & CStr(j) & " = " & s
                    max = n
                End If
            End If
        Next
    Next
End Sub

D:\Project Euler\Problem 004>cscript //nologo 003.vbs
993 * 913 = 906609
CNT = 2291
MAX = 906609

たとえば、現在の最大値が i=993, j=913 の場合、 i≦913 の場合を計算しても仕方ないので

Option Explicit
 
Private cnt: cnt = 0
Private max: max = 0
 
Call main
 
WScript.Echo "CNT = " & cnt
WScript.Echo "MAX = " & max
 
Private Sub main()
    Dim m: m = 0
    Dim i
    For i = 999 To 900 Step -1
        If i = m Then Exit For
 
        Dim j
        For j = i To 900 Step -1
            Dim n: n = i * j
            If n < max Then Exit For
             
            cnt = cnt + 1

            Dim s: s = CStr(n)
            If s = StrReverse(s) Then
                If max < n Then
                    WScript.Echo CStr(i) & " * " & CStr(j) & " = " & s
                    max = n
                    m = j
                End If
            End If
        Next
    Next
End Sub

D:\Project Euler\Problem 004>cscript //nologo 004.vbs
993 * 913 = 906609
CNT = 2291
MAX = 906609

最初の回文数を取得した時点で終了
（結果として正しい解が得られるし、断然速いが、何故これでＯＫなのか説明できない...）

Option Explicit
 
Private cnt: cnt = 0
Private max: max = 0
 
Call main
 
WScript.Echo "CNT = " & cnt
WScript.Echo "MAX = " & max
 
Private Sub main()
    Dim i
    For i = 999 To 900 Step -1
        Dim j
        For j = i To 900 Step -1
            cnt = cnt + 1
 
            Dim n: n = i * j
            Dim s: s = CStr(n)
            If s = StrReverse(s) Then
                If max < n Then
                    WScript.Echo CStr(i) & " * " & CStr(j) & " = " & s
                    max = n
                    Exit Sub
                End If
            End If
        Next
    Next
End Sub

D:\Project Euler\Problem 004>cscript //nologo 005.vbs
993 * 913 = 906609
CNT = 666
MAX = 906609

2桁の数の積の場合

	99	98	97	96	95	94	93	92	91	90
99	9801	9702	9603	9504	9405	9306	9207	9108	9009	8910
98	9702	9604	9506	9408	9310	9212	9114	9016	8918	8820
97	9603	9506	9409	9312	9215	9118	9021	8924	8827	8730
96	9504	9408	9312	9216	9120	9024	8928	8832	8736	8640
95	9405	9310	9215	9120	9025	8930	8835	8740	8645	8550
94	9306	9212	9118	9024	8930	8836	8742	8648	8554	8460
93	9207	9114	9021	8928	8835	8742	8649	8556	8463	8370
92	9108	9016	8924	8832	8740	8648	8556	8464	8372	8280
91	9009	8918	8827	8736	8645	8554	8463	8372	8281	8190
90	8910	8820	8730	8640	8550	8460	8370	8280	8190	8100

大きい数から順に、回文数かどうかチェックするなら、

	99
99	9801

	99	98
99		9702
98

	98	97
99		9603
98	9604
97

	97	96
99		9504
98	9506
97
96

の順に計算すべきだが、それだと解を得るまでの計算量が多くなる

	99	98	97	96	95	94	93	92	91
99	9801	9702	9603	9504	9405	9306	9207	9108	9009
98		9604	9506	9408	9310	9212	9114	9016
97			9409	9312	9215	9118	9021
96				9216	9120	9024
95					9025
94
93
92
91

何故、これだけの計算で解が得られるのか？

	99	98	97	96	95	94	93	92	91
99	9801	9702	9603	9504	9405	9306	9207	9108	9009

明日に続く...