Created
August 17, 2010 20:47
-
-
Save davidxkr/531941 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| require 'benchmark' | |
| class Euler14Recursive | |
| def initialize | |
| @chain_size = 0 | |
| end | |
| def euler_chain_recursive(number) | |
| @chain_size += 1 | |
| return 1 if number == 1 | |
| number = number.even? ? number / 2 : 3 * number + 1 | |
| return euler_chain_recursive(number) | |
| end | |
| def found_the_longest_chain_for(number) | |
| max_chain, cad = 0, 0 | |
| 1.upto(number) do |i| | |
| self.euler_chain_recursive i | |
| if @chain_size > max_chain | |
| max_chain = @chain_size | |
| cad = i | |
| end | |
| @chain_size = 0 | |
| end | |
| cad | |
| end | |
| end | |
| class Euler14Iterative | |
| def euler_chain_iterative(number) | |
| chain_size = 0 | |
| while number != 1 | |
| number = number.even? ? number / 2 : 3 * number + 1 | |
| chain_size += 1 | |
| end | |
| chain_size | |
| end | |
| def found_the_longest_chain_for(number) | |
| max_chain, chain_size, cad = 0, 0, 0 | |
| 1.upto(number) do |i| | |
| chain_size = self.euler_chain_iterative i | |
| if chain_size > max_chain | |
| max_chain = chain_size | |
| cad = i | |
| end | |
| chain_size = 0 | |
| end | |
| cad | |
| end | |
| end | |
| class Euler14IterativeMemory | |
| def initialize | |
| @chains = {} | |
| end | |
| def euler_chain_iterative_with_memory(number) | |
| chain_size = 0 | |
| while number != 1 | |
| chain_size += 1 | |
| number = number.even? ? number / 2 : 3 * number + 1 | |
| if @chains.has_key?(number) | |
| chain_size += @chains[number] | |
| break | |
| end | |
| end | |
| chain_size | |
| end | |
| def found_the_longest_chain_for(number) | |
| max_chain, chain_size, cad = 0, 0, 0 | |
| 1.upto(number) do |i| | |
| chain_size= self.euler_chain_iterative_with_memory i | |
| @chains[i] = chain_size | |
| if chain_size > max_chain | |
| max_chain = chain_size | |
| cad = i | |
| end | |
| chain_size = 0 | |
| end | |
| cad | |
| end | |
| end | |
| Benchmark.bm do |x| | |
| x.report('Recurisvo') do | |
| p = Euler14Recursive.new | |
| p.found_the_longest_chain_for 1_000_000 | |
| end | |
| x.report('Iterativo') do | |
| p = Euler14Iterative.new | |
| p.found_the_longest_chain_for 1_000_000 | |
| end | |
| x.report('Iterativo 2') do | |
| p = Euler14IterativeMemory.new | |
| p.found_the_longest_chain_for 1_000_000 | |
| end | |
| end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment