子供の算数の問題でも、けっこうコンピュータで解くの難しい
問題をみかけたので、ちょっと解いてみた
問題。
「任意の自然数の各桁を、一桁になるまで掛け算する回数の最大回数とその数を示せ。最大桁数を出した生徒には賞品が出ます」
例えば、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
'バケツの整理。4は2の2つ分、8は2の3つ分、9は3の2つ分
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,7。1は無視でよい。
'なんかこの辺を考えたら数学的に色々解けそうだけど今回無視。
'実際に掛け算を行う。
'べき乗使えって話だけどもうなんか高速化めんどくなってる。
Dim decKakezan As Decimal = 1
'"0"と"1"は掛け算しないので2~9。
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
この記事が気に入ったらサポートをしてみませんか?