【アルゴリズム】例題を考えてみたけど難しすぎて挫折した。。

アルゴリズムを色々と考えてきたのですが、
3時間かかって考えたクイックソートが10要素のソートに38秒かかるとか

自分の知性を如実に反映したプログラミング結果になっていて、
お天道様も真っ青な状態です。

ま、考えてきたと言っても3日間だけだけどね。。。

なぜアルゴリズムをさっと書けない？

2時間も3時間もかかって、再帰関数とか書いてる状態。

なんでこんなにだめなのかなーって考えてたんだけど、
小さく書いて小さく実行が出来てないからだと、思う。

問題を見ていきなり「i,jを使って・・・再帰で・・・」なんて考えていて
自分の身の丈にあってない一発でスマートな解答を作ろうとして
こけていたんだと思われる。

考えた問題

こんな問題を考えてみよう

数が二つ与えられて、片方の数字を、
もう片方の数字以下の数字の組み合わせで表現する

（例）
１０　と　１　⇒[1,1,.....,1]
４　と　３　⇒[3,1][2,2][2,1,1][1,1,1,1]
４　と　２　⇒[2,2][2,1,1][1,1,1,1]

伝わったかな。

それでは小さく書いて小さく実行、を意識して解答してみるぞ！

数値クラスへの特異メソッド追加

class Fixnum
	def separate(int)
	p "jjj"
	end
end

1.separate(1)

jjj

よし。

引数を１で固定

class Fixnum
	def separate(int)
		results = []
		if int == 1 then
			results << {1 => self}
		end
		results
	end
end
p 10.separate(1)

[{1=>10}]

よし。

Fixnum特異クラスの方針を変更

class Fixnum
	attr_accessor :results
  def initialize
    @results = []  ←数値のinitializeは実行されないため、このコードは実行されない
  end
  
	def separate(int)
		if int == 1 then
			@results << {1 => self}　←nilがレシーバとなり<<メソッドを実行するためエラー
		end
		
		@results
	end
end

p 10.separate(1)　　←エラー。

数値クラスのinitializeが実行できない。
考えてもいいけど、トリッキーにもなるので、この方針はやめ。

インスタンス変数を使う

class Hoge
	attr_accessor :results
  def initialize
    @results = [] 
  end
  
	def separate(subject, int)
		if int == 1 then
			@results << {1 => subject}
		end
		
		@results
	end
end

p Hoge.new.separate(10,1)

[{1=>10}]

Hogeのインスタンスを作っているところが、煩雑なコードと言う気がするけれど、
アルゴリズムを考えたいので、今はこれで書いていく。

お手上げ

4時間かかっても分からなかった、、だめだ。
紙に書いたりして整理してみたけど、ステップバイステップで進めていくのは難しい。

問題が難しすぎたのかな。。
while文の中で再帰をしていたり、難解なコードになりすぎてる。

↓挫折したコード

class Hoge
attr_accessor :results
	def initialize
		@results = []
	end
	def separate(subject, int)
		int = subject if subject < int
		while int > 0
			result = []
			if int == 1
				result << {1 => subject}
			else
				i = subject / int
				while i >= 0
					_result = []
					_result << {int => i} if i != 0
					if subject - int*i != 0
						separate(subject - int*i, int-1).each do |s|
							_result << s
							@results << _result
						end
					else
						@results << _result
					end
					i -= 1
				end
				
			end
			int -= 1
		end
		result
	end
end

hoge = Hoge.new
hoge.separate(5,5)
p hoge.results

■実行結果

[[{5=>1}], [{4=>1}, {1=>1}], [{2=>1}], [{1=>2}], [{3=>1}, {1=>2}], [{2=>2}, {1=>1}], [{2=>1}, {1=>3}], [{1=>5}], [{1=>5}], [{2=>2}, {1=>1}], [{2=>1}, {1=>3}], [{1=>5}], [{1=>5}], [{2=>1}], [{1=>2}], [{3=>1}, {1=>2}], [{2=>2}, {1=>1}], [{2=>1}, {1=>3}], [{1=>5}], [{1=>5}], [{2=>2}, {1=>1}], [{2=>1}, {1=>3}], [{1=>5}], [{1=>5}], [{4=>1}, {1=>1}], [{2=>1}], [{1=>2}], [{3=>1}, {1=>2}], [{2=>2}, {1=>1}], [{2=>1}, {1=>3}], [{1=>5}], [{1=>5}], [{2=>2}, {1=>1}], [{2=>1}, {1=>3}], [{1=>5}], [{1=>5}], [{2=>1}], [{1=>2}], [{3=>1}, {1=>2}], [{2=>2}, {1=>1}], [{2=>1}, {1=>3}], [{1=>5}], [{1=>5}], [{2=>2}, {1=>1}], [{2=>1}, {1=>3}], [{1=>5}]]

だめだ。。
師匠にヒントをもらおう。