フロイドの循環検出法

フロイドの循環検出法.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 252,
   "id": "4bdd6752",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.(3)\n",
      "0.(142857)\n",
      "0.017(857142)\n"
     ]
    }
   ],
   "source": [
    "# １手順ずつ割って行って同じ余りが出てきたらそこで循環したと判定\n",
    "\n",
    "def getCycleDecimal(target, divitor):\n",
    "  culc_list = []\n",
    "  first_target = target\n",
    "  decimal_pos = len(str(first_target // divitor))\n",
    "\n",
    "  while True:\n",
    "    quotient = target // divitor\n",
    "    remainder = target % divitor\n",
    "\n",
    "    if remainder == 0:\n",
    "      # 割り切れる場合\n",
    "      return first_target / divitor\n",
    "\n",
    "    if (remainder in [i[0] for i in culc_list]):\n",
    "      # 循環まで到達した場合\n",
    "      res = ''\n",
    "      for [culc_remainder, culc_quotient] in culc_list:\n",
    "        res += str(culc_quotient)\n",
    "        if len(res) == decimal_pos:\n",
    "          res += '.'\n",
    "        if (culc_remainder == remainder):\n",
    "          res += '('\n",
    "      return res + str(quotient) + ')'\n",
    "\n",
    "    culc_list.append([remainder, quotient])\n",
    "    target = remainder * 10 # 余りの10倍が次のターゲット\n",
    "\n",
    "print(getCycleDecimal(1, 3))\n",
    "print(getCycleDecimal(1, 7))\n",
    "print(getCycleDecimal(1, 56))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 302,
   "id": "7c8b9857",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.(3)\n",
      "0.(142857)\n",
      "0.017(857142)\n"
     ]
    }
   ],
   "source": [
    "# フロイドの循環検出法\n",
    "\n",
    "def getCycleDecimal(target, divitor):\n",
    "  decimal_pos = len(str(target // divitor))\n",
    "  res = ''\n",
    "\n",
    "  tortoise_next_target = rabbit_next_target = target\n",
    "  while True:\n",
    "    [_, tortoise_remainder] = getQuotientAndRemainder(tortoise_next_target, divitor, 1) # 1つずつ進む\n",
    "    [_, rabbit_remainder] = getQuotientAndRemainder(rabbit_next_target, divitor, 2) # 2つずつ進む\n",
    "\n",
    "    tortoise_next_target = tortoise_remainder * 10\n",
    "    rabbit_next_target = rabbit_remainder * 10\n",
    "\n",
    "    if tortoise_remainder == rabbit_remainder:\n",
    "      break\n",
    "\n",
    "  rabbit_next_target = target # うさぎは最初のターゲットに戻る\n",
    "  while True:\n",
    "    [_, tortoise_remainder] = getQuotientAndRemainder(tortoise_next_target, divitor, 1) # 続きから1つづつ進む\n",
    "    [quotient, rabbit_remainder] = getQuotientAndRemainder(rabbit_next_target, divitor, 1) # 最初のターゲットから1つずつ進む\n",
    "\n",
    "    res += str(quotient)\n",
    "    if len(res) == decimal_pos:\n",
    "      res += '.'\n",
    "\n",
    "    tortoise_next_target = tortoise_remainder * 10\n",
    "    rabbit_next_target = rabbit_remainder * 10\n",
    "\n",
    "    if tortoise_remainder == rabbit_remainder:\n",
    "      res += '('\n",
    "      break\n",
    "\n",
    "  while True:\n",
    "    [quotient, rabbit_remainder] = getQuotientAndRemainder(rabbit_next_target, divitor, 1)\n",
    "    res += str(quotient)\n",
    "    \n",
    "    rabbit_next_target = rabbit_remainder * 10\n",
    "\n",
    "    if tortoise_remainder == rabbit_remainder:\n",
    "      res += ')'\n",
    "      break\n",
    "    \n",
    "  return res\n",
    "\n",
    "def getQuotientAndRemainder(target, divitor, count):\n",
    "  for i in range(count):\n",
    "    quotient = target // divitor\n",
    "    remainder = target % divitor\n",
    "    target = remainder * 10\n",
    "  return [quotient, remainder]\n",
    "\n",
    "print(getCycleDecimal(1, 3))\n",
    "print(getCycleDecimal(1, 7))\n",
    "print(getCycleDecimal(1, 56))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}