面接問題-まとめ

require "rubygems"

##
#1.平衡点の問題
#平衡点:int[]numbers={1,3,5,7,8,25,4,20}25の前の総和は24で、25の後の総和も24で、25という点が平衡点です.配列内の要素が前の部分が後ろの部分に等しい場合、この点のシーケンスは平衡点です.
#要件:任意の平衡点を返す

puts "     " + "* " * 20

#     
numbers = [1, 3, 5, 7, 8, 25, 4, 20]
len = numbers.size - 1
head_sum = 0;tail_sum = 0
head= 0;tail =len

#    
for i in 0..len
  (puts "mid is :#{numbers[i]} sum is:#{head_sum}";break) if head_sum.eql?(tail_sum) and head_sum > 0
  (head_sum += numbers[head];head += 1) if head_sum <=tail_sum
  (tail_sum += numbers[tail]; tail -= 1) if tail_sum <= head_sum
end

##
#2.支配点問題:
#支配数:配列内のある要素の出現回数が配列総数の半分より大きい場合に支配数となり、その位置順が支配点となる.例えばint[]a={3,3,1,2,3};3は支配数、0、1、4はそれぞれ支配点である.

puts "     " + "* " * 20

h_count = {} #      
h_index = {} #      
Hash
a = [3,3,1,2,3]
a.each_index do |i|
  h_count[a[i]]=0 if h_count[a[i]].nil?  
  h_count[a[i]] += 1
  h_index[a[i]] = [] if h_index[a[i]].nil?
  h_index[a[i]] << i
end

list = h_count.sort {|a,b| b[1]<=> a[1]}
puts "    :#{list[0][0]}   :#{list[0][1]}"
puts "    :#{h_index[list[0][0]].join(",")}"

##
#3.最大公約数、転がり相除算

a,b = 5767,4453
... temp = a
... while temp:
...     temp = a % b
...     if temp == 0:
...       print b
...     else:
...         print a,b
...         
...     a = b
...     b = temp

最小公倍数さいしょうこうばいすう:数式ほうていしき
甲、乙の2つの自然数とそれらの最大公約数は最小公倍数と以下の関係があることを証明することができる.
甲×乙=最大公約数×公倍数の最小値は、次のようになります.
最小公倍数=A×乙÷最大公約数は2つの数の最小公倍数を求める.
##
#4.大数剰余を求める
原理は大きい数を分けて計算して、位によって計算します
23 = 2*10 + 3
23%n = 2%n*10 + 3%n

d = 1232132131
f = 7
mod = 0
... for i in str(d):
...     mod = mod * 10 + int(i)
...     mod = mod % f
...     print mod,f