LoginSignup
17
6

More than 5 years have passed since last update.

@ChanJun(Inoue Jun)in株式会社qnote

社内勉強会で比率計算を書いてみた話

Last updated at Posted at 2018-10-22

はじめに

画像の拡大・縮小など、比率を維持して値を変更するという場面があると思います。
今回はそんな状況を想定して下記の問題を、若手社員と一緒にもくもく解いてみました。
ちなみにネットを検索するとそのもの答えが出てしまいそうなので、ネット検索は禁止としました。

問題

  1. 2つの整数値x,yの比率を求めよう
  2. x,yのいずれか大きい方を任意の最大値maxとして拡大/縮小した値を求めよう

解法1：除法

まずはもっともお手軽な方法として、単純な除法を用いて比率を求める案がでました。

例.
x = 100
y = 10
x / y = 10
xはyの10倍
つまりx:y=10:1

直感的でわかりやすいとは思うのですが、この方法では割り切れない場合が出て来たときに正確性が失われるというデメリットがあります。

例.
x = 100
y = 30
x / y = 3.3333...
xはyの約3倍？

この場合、本来は「x : y = 10 : 3」で良いはずですが、単純な除法を使って求めた比率では、後に続く問題でmaxを500とした場合にyが150とならないという問題が発生してしまいます。
誤差の許容度次第で端数処理で対応するというのもアリだとは思います。
※計算を逆にすることで対応可能なケースもありますが例としては割愛します。

解法2：最大公約数

次に事前に用意していた解法として、最大公約数でx,yそれぞれを割ることで比率を求める方法を提示しました。

例.
x = 100
y = 30
最大公約数 = 10
x : y = x / 最大公約数 : y / 最大公約数
つまりx:y=10:3

この方法であれば、整数で比率を出すことができるようになります。

ユークリッドの互除法

最大公約数を求める方法として「ユークリッドの互除法」を利用することにしました。

一応簡単にまとめると下記手順の繰り返しになります。

  1. 大きい値を小さい値で割る
  2. 余りが出たら元の小さい値を出て来た余りで割る

再帰とループ

繰り返し処理の書き方としては再帰とループという2つの方法があります。
再帰はスタックオーバーフローの心配がありますが、スッキリとしたコードを書くことができます。
一方ループは冗長なコードとなる可能性と、条件が複雑になった場合に見通しが悪くなってしまう可能性があります。
また、どちらも抜けるための条件を誤ると無限ループに陥ることに注意が必要です。
※再帰のスタックオーバーフローに関しては詳しく書きません。

末尾呼び出しの最適化

最近の言語では、再帰のスタックオーバーフローを末尾呼び出しの最適化によって解消できることがあります。
ただし、これは言語(のコンパイラ)機能なのでどんな言語でも解決してくれるわけではないので実装を検討する際に合わせて考えてください。

今回の場合

Kotlinでのみですが、フィボナッチ数を利用して確認してみました。

val x = 1836311903
val y = 1134903170

上記がInt指定できる最大の最大のフィボナッチ数の組合せで、これを使用した場合でも試行回数は45回しかかかりませんでした。
したがって今回のケースでは特に意識する必要なく再帰もループも使えそうだということがわかりました。

ただし、実案件ベースで考えた時の再帰というのは考えものです。
若手からベテランまで、プログラムへの理解度が様々のチームなどでは、今回の問題のようなシンプルな繰り返し処理ではループの方がレベルを問わず理解しやすいのでは？という結論となりました。
当然複雑になればループでも理解しづらくなってくるので、再帰を含め可読性を高める方法を検討する必要はあります。

コード例

以下は今回の問題を各言語で書いてもらったものを比較しやすいように書き換えたコードです。
※問題2の答えは誤差が出るケースがありますが、対処はケースにより異なると思いますので特に対処しないコードになっています。

Kotlin

fun main(args: Array<String>) {
  val x = 30
  val y = 100
  val max = 500

  val gcdResult = gcd(x, y)
  val xRatio = x / gcdResult
  val yRatio = y / gcdResult
  println("最大公約数: $gcdResult => $xRatio:$yRatio")

  val largeResult = max
  val smallResult = getSmallerGcdPair(x, y, largeResult)
  if(x > y) {
    println("$x:$y => $largeResult:$smallResult")
  } else {
    println("$x:$y => $smallResult:$largeResult")
  }
}

fun gcd(xInput: Int, yInput: Int): Int {
  var largeVal = Math.max(xInput, yInput)
  var smallVal = Math.min(xInput, yInput)
  var remVal = 0

  do{
    remVal = largeVal % smallVal
    largeVal = smallVal
    smallVal = remVal
  } while(remVal > 0)

  return largeVal
}

fun getSmallerGcdPair(xRatio: Int, yRatio: Int, largeResult: Int): Int {
  var largeRatio = Math.max(xRatio, yRatio)
  var smallRatio = Math.min(xRatio, yRatio)

  return largeResult / largeRatio * smallRatio    
}

Swift

func main() {
  let x: Int = 30
  let y: Int = 100
  let max = 500

  let gcdResult = gcd(x, y)
  let xRatio = x / gcdResult
  let yRatio = y / gcdResult
  print("最大公約数: \(gcdResult) => \(xRatio) : \(yRatio)")

  let largeResult = max
  let smallResult = getSmallerGcdPair(xRatio, yRatio, largeResult)
  if(x > y) {
    print("\(x):\(y) => \(largeResult):\(smallResult)")
  } else {
    print("\(x):\(y) => \(smallResult):\(largeResult)")
  }
}

func gcd(_ xInput: Int, _ yInput: Int) -> Int {
  var largeVal = max(xInput, yInput)
  var smallVal = min(xInput, yInput)
  var remVal = 0

  repeat {
    remVal = largeVal % smallVal
    largeVal = smallVal
    smallVal = remVal
  } while remVal > 0

  return largeVal
}

func getSmallerGcdPair(_ xRatio: Int, _ yRatio: Int, _ largeResult: Int) -> Int {
  let largeRatio = max(xRatio, yRatio)
  let smallRatio = min(xRatio, yRatio)

  return largeResult / largeRatio * smallRatio
}

main()

PHP

<?php
const x = 30;
const y = 100;
const max = 500;

define('gcdResult', gcd(x, y));
define('xRatio', x / gcdResult);
define('yRatio', y / gcdResult);
echo "最大公約数: ".gcdResult." => ".xRatio.":".yRatio.PHP_EOL;

const largeResult = max;
define('smallResult', getSmallerGcdPair(xRatio, yRatio, largeResult));
if(x > y) {
  echo x.":".y." => ".largeResult.":".smallResult.PHP_EOL;
} else {
  echo x.":".y." => ".smallResult.":".largeResult.PHP_EOL;
}

function gcd($xInput, $yInput): int {
  $largeVal = max($xInput, $yInput);
  $smallVal = min($xInput, $yInput);
  $remVal = 0;

  do {
    $remVal = $largeVal % $smallVal;
    $largeVal = $smallVal;
    $smallVal = $remVal;
  } while($remVal > 0);

  return $largeVal;
}

function getSmallerGcdPair($xRatio, $yRatio, $largeResult): int {
  define('largeRatio', max($xRatio, $yRatio));
  define('smallRatio', min($xRatio, $yRatio));

  return $largeResult / largeRatio * smallRatio;
}

JavaScript

function main() {
  const x = 30
  const y = 100
  const max = 500

  const gcdResult = gcd(x, y)
  const xRatio = x / gcdResult
  const yRatio = y / gcdResult
  console.log(`最大公約数: ${gcdResult} => ${xRatio} : ${yRatio}`)

  const largeResult = max
  const smallResult = getSmallerGcdPair(xRatio, yRatio, largeResult)
  if(x > y) {
    console.log(`${x}:${y} => ${largeResult}:${smallResult}`)
  } else {
    console.log(`${x}:${y} => ${smallResult}:${largeResult}`)
  }
}

const gcd = (xInput, yInput) => {
  let largeVal = Math.max(xInput, yInput)
  let smallVal = Math.min(xInput, yInput)
  let remVal = 0

  do {
    remVal = largeVal % smallVal
    largeVal = smallVal
    smallVal = remVal
  } while(remVal > 0)

  return largeVal
}

const getSmallerGcdPair = (xRatio, yRatio, largeResult) => {
  const largeRatio = Math.max(xRatio, yRatio)
  const smallRatio = Math.min(xRatio, yRatio)

  return largeResult / largeRatio * smallRatio
}

main()

Java

import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    final int x = 30;
    final int y = 100;
    final int max = 500;

    final int gcdResult = gcd(x, y);
    final int xRatio = x / gcdResult;
    final int yRatio = y / gcdResult;
    System.out.println("最大公約数: " + gcdResult + " => " + xRatio + " : " + yRatio);

    final int largeResult = max;
    final int smallResult = getSmallerGcdPair(x, y, largeResult);
    if(x > y) {
      System.out.println(x + ":" + y + " => " + largeResult + ":" + smallResult);
    } else {
      System.out.println(x + ":" + y + " => " + smallResult + ":" + largeResult);
    }
  }

  private static int gcd(int xInput, int yInput) {
    int largeVal = Math.max(xInput, yInput);
    int smallVal = Math.min(xInput, yInput);
    int remVal = 0;

    do {
      remVal = largeVal % smallVal;
      largeVal = smallVal;
      smallVal = remVal;
    } while(remVal > 0);

    return largeVal;
  }

  private static int getSmallerGcdPair(int xRatio, int yRatio, int largeResult) {
    final int largeRatio = Math.max(xRatio, yRatio);
    final int smallRatio = Math.min(xRatio, yRatio);

    return largeResult / largeRatio * smallRatio;
  }
}

コードを比較してみる

シンプルなコードであることもあり、普段関わっていない言語でも意識せずに読むことができるかと思います。
言語毎の書き方の癖も確かにありますが、逆に言えば違いはそれだけのようにも感じられます。

まとめ

  • 単純な除法では正確な比率を求められないケースがある
  • 最大公約数を利用すれば整数比を求めることができる
  • 再帰よりループの方が理解はしやすい
    • 複雑になるようなら再帰を含めた可読性の向上を考える
  • 普段関わらない言語でも読んでみるとあっさり理解できてしまうかも

おまけ

Kotlinだけですが、最大公約数を出す再帰での書き方を一応書いておきます。

gcd(Math.max(x, y), Math.min(x, y))
tailrec fun gcd(largeInput: Int, smallInput: Int): Int 
  = if(smallInput == 0) largeInput else gcd(smallInput, largeInput % smallInput)
17
6
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
17
6