見出し画像

子供の算数の問題でも、けっこうコンピュータで解くの難しい

問題をみかけたので、ちょっと解いてみた

問題。
「任意の自然数の各桁を、一桁になるまで掛け算する回数の最大回数とその数を示せ。最大桁数を出した生徒には賞品が出ます」
例えば、15なら1x5=5で1回。93なら9x3=27, 2x7=14, 1x4=3と3回という具合。

とりあえずプログラムで、特に大した高速化も考えずにやってみてる。

言語はVisualBasic.NET。
この言語にしたのには色々理由がありますが、コード貼っておきます。
もっと工夫ができたり、高速化ができたり、数式で答えが出せれたら、また追記するかも。

とりあえず今はSSDがあるので、パターン等のメモをSSDに送りまくれば、桁数がでかくなった場合にも計算が早そうだけど、いずれにせよ2^96をこの速度で追っかけてもダメですね……。

Option Strict On

Imports System.Text
Imports System.IO
Imports System.Collections.Generic

Public Class Form1

   Private Sub Button1_Click_1(ByVal sender As Object, ByVal e As EventArgs) Handles Button1.Click

       Const FileName1 As String = "C:\hoge\計算結果.csv"
       Const FileName2 As String = "C:\hoge\計算経過.csv"

       '過去の計算結果のメモ用(OutOfMemoryの具合と調節……)
       Dim dicKeisan As New Dictionary(Of String, Decimal)

       Using sw As New System.IO.StreamWriter(FileName1, False, System.Text.Encoding.GetEncoding("Shift_JIS"))
           Using sw2 As New System.IO.StreamWriter(FileName2, False, System.Text.Encoding.GetEncoding("Shift_JIS"))

               Dim DecMaxKaisuu As Decimal = 0 '過去最高の「計算回数」
               Dim motodecNumber As Decimal = 0

               '巨大な数の整数まで、「計算回数」を調べる。
               For decNumber = 0 To Decimal.MaxValue
                   '検算用
                   'For decNumber = 0 To 1000

                   '進捗状況を時々ファイルに書き出す
                   If decNumber Mod 1000000 = 0 Then
                       sw2.WriteLine("")
                   End If

                   Dim decKaisuu As Decimal = 0 '「計算回数」
                   Dim strNumber As String = decNumber.ToString '文字列で処理
                   Dim motostrNumber As String = strNumber '計算結果メモ用に保存

                   '各桁を掛け算し、1桁になるまで繰り返す
                   Do
                       '掛け算を行い、掛け算した結果の文字列を元の文字列に入れる
                       strNumber = Kakezan(strNumber.ToString)
                       '掛け算した回数を1増やす
                       decKaisuu += 1
                       '1桁になったら終了
                       If strNumber.Length = 1 Then
                           Exit Do
                       End If
                       '掛け算でオーバーフローだった場合、結果未定とする
                       If strNumber = "OverFlow" Then
                           decKaisuu = -1
                           Exit Do
                       End If
                       '計算結果メモがあれば、その後の計算をせずにメモを使う。
                       'オーバーフロー対策と若干の速度対策。ただしメモリを使う。
                       If dicKeisan.ContainsKey(strNumber) = True Then
                           decKaisuu += dicKeisan.Item(strNumber)
                           If dicKeisan.Item(strNumber) = -1 Then
                               decKaisuu = -1
                               Exit Do
                           End If
                           Exit Do
                       End If
                   Loop

                   '最高計算回数更新の場合(特に出力していない)
                   If decKaisuu > DecMaxKaisuu Then
                       DecMaxKaisuu = decKaisuu
                   End If

                   ''検算用
                   'If decKaisuu > 0 Then

                   '計算回数が一定以上の場合、メモする。
                   If decKaisuu > 10 Then
                       'OutOfMemoryや桁あふれ対策でバランス……
                       dicKeisan.Add(motostrNumber, decKaisuu)
                   End If

                   '検算用
                   'If decKaisuu > 0 Then

                   '計算結果が一定以上の場合、ファイルに出力する。
                   If decKaisuu > 9 Then
                       sw.WriteLine(motostrNumber & "," & decKaisuu.ToString)
                   End If
               Next

           End Using
       End Using

   End Sub


   'String型で与えられた「数字」の各位の数を全て掛け合わせた結果を文字列で返す。
   '引数:String型
   '戻り値:String型
   Private Function Kakezan(ByVal strNumber As String) As String
       '0~9の数字がいくつ含まれているかを表すバケツ
       Dim decSuuji() As Decimal = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

       '各位の数字を数をバケツに放り込む
       For i As Integer = 0 To strNumber.Length - 1
           decSuuji(Convert.ToInt32(Mid(strNumber, i + 1, 1))) += 1
           'どこかの位に0があれば計算結果は0
           If decSuuji(0) > 0 Then
               Return "0"
           End If
       Next

       'バケツの整理。422つ分、823つ分、932つ分
       decSuuji(2) += decSuuji(4) * 2
       decSuuji(4) = 0
       decSuuji(2) += decSuuji(8) * 3
       decSuuji(8) = 0
       decSuuji(3) += decSuuji(9) * 2
       decSuuji(9) = 0
       '6は2と3に
       decSuuji(2) += decSuuji(6)
       decSuuji(3) += decSuuji(6)
       decSuuji(6) = 0


       'このへんの処理は文字列読み込み中にやる方が速いのか試してない。

       '2×5(2は4も6も8も含む)に分解できる場合には、次の計算で必ず終わるので、それを返す。
       If (decSuuji(2) > 0) And (decSuuji(5)) > 0 Then
           Return "10"
       End If

       '残った数字は1,2,3,5,71は無視でよい。
       'なんかこの辺を考えたら数学的に色々解けそうだけど今回無視。


       '実際に掛け算を行う。
       'べき乗使えって話だけどもうなんか高速化めんどくなってる。
       Dim decKakezan As Decimal = 1

       '"0""1"は掛け算しないので29。
       For i As Integer = 2 To 9
           'バケツの中身を掛けていく。
           'オーバーフローしたらごめんなさいと謝る。
           Dim j As Decimal = 0
           Do While j < decSuuji(i)
               Try
                   decKakezan *= i
               Catch ex As Exception
                   Return "OverFlow"
               End Try
               j += 1
           Loop
       Next

       '掛け算した結果の数字を文字列型に変換して返す。
       Return decKakezan.ToString

   End Function

End Class



この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

ありがとうございます(´ω`*)
5

とつげき東北

ベストセラー戦術書『科学する麻雀(https://amzn.to/2Qz6B2J )』著者。 元東京大学非常勤講師。ウィキペディア(http://bit.ly/d9s4CU )。 totutohoku@hotmail.com の中の人をマネしてるようだ。

プログラムとか数学、技術とか

1つ のマガジンに含まれています
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。