150227

Ruby


計算

今更だが、通常割り算の計算は切り捨てだが、
切り捨てをしないままにするにはmathnを使えば良い。

require 'mathn'

p 5 / 3
p 5 / 3 + 5 / 3 + 5 / 3

出力結果は
1
3
ではなく、
(5/3)
5
となる。

150225

Ruby


Square-free integer

m未満のsquare-freeな整数の個数を出力するコードを書いてみた。

オンライン整数列大辞典の
A005117（http://oeis.org/A005117/list）

と比較し、答え合わせしてみる。

require 'prime'

N0 = 113

N  = 101

# m未満のsquare-freeな整数の個数

def number_of_squarefree_numbers(m , n = m)

  s = 0

  Prime.each{|x|

    break if x * x >= m || x >= n

    s += number_of_squarefree_numbers((m - 1) / (x * x) + 1, x)

  }

  return m - 1 - s

end

for i in (1..N)

  p [i, number_of_squarefree_numbers(i + 1, )]

end

# OEIS A005117との比較用

ary = []

fn = 0

for i in (1..N0)

  bn = number_of_squarefree_numbers(i + 1, )

  ary << i if fn != bn

  fn = bn

end

# OEIS A005117のデータ

ary0 =

[1,2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,

 30,31,33,34,35,37,38,39,41,42,43,46,47,51,53,55,

 57,58,59,61,62,65,66,67,69,70,71,73,74,77,78,79,

 82,83,85,86,87,89,91,93,94,95,97,101,102,103,105,

 106,107,109,110,111,113]

# 一致の確認

p ary == ary0

150224(2)

Ruby


Cyclic number

http://en.wikipedia.org/wiki/Cyclic_number

に載っているcyclic numberを出力するコードを書いてみた。

require 'prime'

N = 70

Full_Reptend_Primes = []

Prime.each(N){|pr|

  if pr > 5

    i = 1

    n = 10

    while i < pr - 1 && n != 1

      n *= 10

      n %= pr

      i += 1

    end

    Full_Reptend_Primes << pr if i == pr - 1

  end

}

# cyclic numberの出力

Full_Reptend_Primes.each{|i|

  a = 10 ** (i - 1) / i

  p sprintf("%0*d", i - 1, a)

}

150224

Python


和について

print sum(range(1, 101))
print sum(x for x in range(1, 101))

上二つを比べると、２つ目の方が一般性がある。
例えば、二乗の和に変更したいなら、

print sum(x ** 2 for x in range(1, 101))

とすればよい。

print sum(f(x) for x in xrange( , ))

の形で覚えていてもいいかもしれない。

150118

Ruby


「アルゴリズムとデータ構造」のRuby版。

２分木を使ったマップ

# -*- coding: cp932 -*-

# Node Class

class Node

  attr_accessor :key, :value, :left, :right

  def initialize(num, val)

    @key = num      # ノードのキー

    @value = val    # ノードが保持する値

    @left = nil     # 左側のノード

    @right = nil    # 右側のノード

  end

end

# ノードを生成する

def create_new_node(num, val)

  newNode = Node.new(num, val)

  return newNode

end

# ノードの追加

def insert_tree(num, val, node)

  # 1つも挿入されていない場合

  if node == nil

    @tree_root = create_new_node(num, val)

    return

  end

  if node.key > num

    if node.left != nil

      insert_tree(num, val, node.left)

    else

      node.left = create_new_node(num, val)

    end

  else

    if node.right != nil

      insert_tree(num, val, node.right)

    else

      node.right = create_new_node(num, val)

    end

  end

end

# ノードの検索

def find_value(node, num)

  if node.key > num

    if node.left == nil

      return nil

    end

    return find_value(node.left, num)

  end

  if node.key < num

    if node.right == nil

      return nil

    end

    return find_value(node.right, num)

  end

  return node

end

# ノードの削除

def delete_tree(num)

  node = @tree_root

  parent_node = nil

  direction = 0

  # while文で削除すべき対象を見つける

  while (node != nil && node.key != num)

    if node.key > num

      parent_node = node

      node = node.left

      direction = -1

    else

      parent_node = node

      node = node.right

      direction = 1

    end

  end

  if node == nil

    return false

  end

  if node.left == nil || node.right == nil

    if node.left == nil

      if direction == -1

        parent_node.left = node.right

      elsif direction == 1

        parent_node.right = node.right

      elsif direction == 0

        @tree_root = node.right

      end

   else

      if direction == -1

        parent_node.left = node.left

      elsif direction == 1

        parent_node.right = node.left

      elsif direction == 0

        @tree_root = node.left

      end

    end

  else

    left_biggest = node.left

    parent_node = node

    direction = -1

    while left_biggest.right != nil

      parent_node = left_biggest

      left_biggest = left_biggest.right

      direction = 1

    end

    node.key = left_biggest.key

    node.value = left_biggest.value

    if direction == -1

      parent_node.left = left_biggest.left

    else

      parent_node.right = left_biggest.left

    end

  end

  return true

end

def print_tree(depth, node = nil)

  if node == nil

    return

  end

  print_tree(depth + 1, node.left)

  i = 0

  while i < depth

    printf ""

    i += 1

  end

  printf("%s ：%s \n", node.key, node.value)

  print_tree(depth + 1, node.right)

end

def main

  action = nil

  while action != 0

    print_tree(0, @tree_root)

    printf("0:終了1:挿入2:探索3:削除>")

    action = gets.chomp.to_i

    case action

      when 1

        printf("挿入する文字列（キー）:>")

        key = gets.chomp.to_i

        printf("キーに対応させる値:>")

        value = gets.chomp

        insert_tree(key, value, @tree_root)

      when 2

        printf("探索する文字列:>")

        i = gets.chomp.to_i

        node_found = find_value(@tree_root, i)

        if node_found != nil

          printf("対応する値は%sです\n", node_found.value)

        else

          printf("見つかりませんでした\n")

        end

      when 3

        printf("削除する文字列:>")

        i = gets.chomp.to_i

        if delete_tree(i)

          printf("削除しました\n")

        else

          printf("見つかりませんでした\n")

        end

    end

  end

end

main

150117

Ruby


「アルゴリズムとデータ構造」のRuby版。

２分木のデータ追加、サーチ、削除

（ただし、書籍のように最初にtreeを作成しません。）

# -*- coding: cp932 -*-

# Node Class

class Node

  attr_accessor :value, :left, :right

  def initialize(val)

    @value = val   # ノードが保持する値

    @left = nil    # 左側のノード

    @right = nil   # 右側のノード

  end 

end

# ノードを生成する

def create_new_node(val)

  newNode = Node.new(val)

  return newNode

end

# ノードの追加

def insert_tree(num, node)

  # 1つも挿入されていない場合

  if node == nil

    @tree_root = create_new_node(num)

    return

  end 

  # num が現在の node の値よりも小さい場合

  if node.value > num

    if node.left != nil

      insert_tree(num, node.left)

    else

      node.left = create_new_node(num)

    end

  # num が現在の node の値以上の場合

  else

    if node.right != nil

      insert_tree(num, node.right)

    else

      node.right = create_new_node(num)

    end

  end

end

# ノードの検索

def find_value(node, val)

  # 自分より小さい値ならば、左側

  if node.value > val

    if node.left == nil

      return nil

    end

    return find_value(node.left, val)

  end

  # 自分より大きい値ならば、右側

  if node.value < val

    if node.right == nil

      return nil

    end

    return find_value(node.right, val)

  end

  return node 

end

# ノードの削除

def delete_tree(val)

  node = @tree_root

  parent_node = nil

  direction = 0

  # while文で削除すべき対象を見つける

  while (node != nil && node.value != val)

    if node.value > val

      parent_node = node

      node = node.left

      direction = -1

    else

      parent_node = node

      node = node.right

      direction = 1

    end

  end

  if node == nil

    return false

 end

  if node.left == nil || node.right == nil

    if node.left == nil

      if direction == -1

        parent_node.left = node.right

      elsif direction == 1

        parent_node.right = node.right

      elsif direction == 0

        @tree_root = node.right

      end

    else

      if direction == -1

        parent_node.left = node.left

      elsif direction == 1

        parent_node.right = node.left

      elsif direction == 0

        @tree_root = node.left

      end

    end

  else

    left_biggest = node.left

    parent_node = node

    direction = -1

    while left_biggest.right != nil

      parent_node = left_biggest

      left_biggest = left_biggest.right

      direction = 1

    end

    node.value = left_biggest.value

    if direction == -1

      parent_node.left = left_biggest.left

    else

      parent_node.right = left_biggest.left

    end

  end

  return true

end

def print_tree(depth, node = nil)

  if node == nil

    return

  end

  print_tree(depth + 1, node.left)

  i = 0

  while i < depth

    printf "   "

    i += 1

  end

  printf("%d\n", node.value)

  print_tree(depth + 1, node.right)

end

def main

  action = nil

  while action != 0

    print_tree(0, @tree_root)

    printf("実行する操作のタイプを入力してください。\n 1 ：追加\t2 ：検索\t3 ：削除\t それ以外：終了>")

    action = gets.chomp.to_i

    case action

      when 1

        printf("1 ～100の範囲で，追加する数字を入力してください:")

        i = gets.chomp.to_i

        if i < 1 || i > 100

          continue

        end

        insert_tree(i, @tree_root)

      when 2

        printf("検索する数字を入力してください:")

        i = gets.chomp.to_i

        if find_value(@tree_root, i) != nil

          printf("%dを発見しました\n", i)

        else

          printf("%dは見つかりませんでした\n", i)

        end

      when 3

        printf("削除する数字を入力してください:")

        i = gets.chomp.to_i

        if delete_tree(i)

          printf("%dを削除しました\n", i)

        else

          printf("%dは見つかりませんでした\n", i)

        end

      else

        break

    end

  end

end

main

150112

Ruby


「アルゴリズムとデータ構造」のRuby版。

リストのなかのデータのサーチと削除。

# -*- coding: cp932 -*-

class TagListNode
  attr_reader :data
  attr_accessor :prev, :next
  def initialize(data)
    @data = data
    @prev = nil
    @next = nil
  end
end

buf = nil
firstnode = nil
lastnode = nil
while buf != 0
  printf("整数を入力してください（0を入力すると終了）:")
  buf = gets().to_i
  if buf != 0
  # 新しいノードを作成
  newnode = TagListNode.new(buf)
  newnode.next = nil
    if lastnode != nil
      # すでにあるリストの末尾に新しいノードをつなげる
      lastnode.next = newnode
      newnode.prev = lastnode
      lastnode = newnode
    else # これが最初の要素だった場合
      firstnode = lastnode = newnode
      newnode.prev = nil
    end
  end
end

buf = nil
while buf != 0
  printf("検索する値を入力してください：")
  buf = gets().to_i
  thisnode = firstnode
  # 最初に入力した値のなかから検索し，見つかったら削除
  while thisnode != nil
    if thisnode.data == buf
      printf("入力された値のなかに%dが見つかりました。ノードを削除します。\n", buf)
      if thisnode.prev != nil
        thisnode.prev.next = thisnode.next
      else
        firstnode = thisnode.next
      end
      if thisnode.next != nil
        thisnode.next.prev = thisnode.prev
      else
        lastnode = thisnode.prev
      end
      break
    end
    thisnode = thisnode.next
  end
  if thisnode == nil
    printf("%dは入力されていないか，あるいはすでに削除されています。\n", buf)
  end
end

150111(3)

Ruby


「アルゴリズムとデータ構造」のRuby版。

リストを使って入力したいくつかの数値とその合計を出力する。

# -*- coding: cp932 -*-

class TagListNode

  attr_reader :data

  attr_accessor :prev, :next

  def initialize(data)

    @data = data

    @prev = nil

    @next = nil

  end

end

buf = nil

firstnode = nil

lastnode = nil

while buf != 0

  printf("整数を入力してください（0を入力すると終了）:")

  buf = gets().to_i

  if buf != 0

  # 新しいノードを作成

  newnode = TagListNode.new(buf)

  newnode.next = nil

    if lastnode != nil

      # すでにあるリストの末尾に新しいノードをつなげる

      lastnode.next = newnode

      newnode.prev = lastnode

      lastnode = newnode

    else # これが最初の要素だった場合

      firstnode = lastnode = newnode

      newnode.prev = nil

    end

  end

end

# 合計値を算出

printf("--入力されたのは以下の数です--\n");

sum = 0

thisnode = firstnode

while thisnode != nil

  printf("%d\t",thisnode.data)

  sum += thisnode.data

  thisnode = thisnode.next

end

printf("\n----\n以上の数の合計値は%dです。\n", sum)

150111(2)

C


簡単な線形リスト

#include <stdio.h>
#include <stdlib.h>

typedef int data_t;

typedef struct nodetag {
    data_t data;
    struct nodetag *next;
} node_t;

main()
{
int i;

node_t nd1, nd2, nd3;
node_t *p;

nd1.data = 1;
nd1.next = &nd2;
nd2.data = 2;
nd2.next = &nd3;
nd3.data = 3;
nd3.next = NULL;

p = &nd1;

for (i = 1; i <= 3; i++){
printf("%d\n", p->data);
p = p->next;
    }
}

150111

Ruby


「アルゴリズムとデータ構造」のRuby版。

バイナリサーチ

# -*- coding: cp932 -*-

NOT_FOUND = -1

N = 10

def binary_search(x, a, left, right)

  while left <= right

    mid = (left + right) / 2

    return mid if a[mid] == x

    if a[mid] < x 

      left = mid + 1

    else

      right = mid - 1

    end

  end

  return NOT_FOUND

end

# 適当な配列を作る

array = []

printf("array ")

printf("[0]:%d ", array[0] = rand(3))

for i in (1..N - 1)

  printf("[%d]:%d ", i, array[i] = array[i - 1] + rand(3))

end

printf("\n何を探しますか:")

i = gets().to_i

r = binary_search(i, array, 0, N - 1)

if r == NOT_FOUND

  printf("%dは見つかりません\n", i)

else

  printf("%dは%d番目です\n", i, r)

end

バイナリサーチ（lower_bound）

# -*- coding: cp932 -*-

NOT_FOUND = -1
N = 10

def binary_search(x, a, left, right)
  while left < right
    mid = (left + right) / 2
    if a[mid] < x
      left = mid + 1
    else
      right = mid
    end
  end
  return left if a[left] == x
  return NOT_FOUND
end

# 適当な配列を作る
array = []
printf("array ")
printf("[0]:%d ", array[0] = rand(3))
for i in (1..N - 1)
  printf("[%d]:%d ", i, array[i] = array[i - 1] + rand(3))
end
printf("\n何を探しますか:")
i = gets().to_i
r = binary_search(i, array, 0, N - 1)
if r == NOT_FOUND
  printf("%dは見つかりません\n", i)
else
  printf("%dは%d番目です\n", i, r)
end