kadai_4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "手持ちのコインの数（500円玉、100円玉、50円玉、10円玉）と、返すべきお釣りの金額が与えられたとき、釣銭を出力するプログラムを書け。もし釣銭が足りなければ「釣銭切れ」とメッセージを出力せよ。例えば、500円玉が2枚、100円玉が4枚、50円玉が3枚、10円玉が4枚手持ちにあるとき、お釣りが280円なら、100円玉×2, 50円玉×1, 10円玉×3が釣銭として出力される。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of 500yen coins2\n",
      "Number of 100yen coins4\n",
      "Number of 50yen coins3\n",
      "Number of 10yen coins4\n",
      "How much is the change280\n",
      "100円玉×2, 50円玉×1, 10円玉×3, "
     ]
    }
   ],
   "source": [
    "coins = [500, 100, 50, 10]\n",
    "numcoin = {}\n",
    "\n",
    "for coin in coins:\n",
    "    num = input('Number of ' + str(coin) + 'yen coins')\n",
    "    numcoin[coin] = int(num)\n",
    "\n",
    "def calcchange(coins, numcoin):\n",
    "    change = int(input('How much is the change'))\n",
    "    numchange = numcoin.copy()\n",
    "    \n",
    "    for coin in coins:\n",
    "        numchange[coin] = 0\n",
    "        if change < coin or numcoin[coin] == 0:\n",
    "            continue\n",
    "        else:\n",
    "            while change >= coin and numcoin[coin] > 0:\n",
    "                numchange[coin] += 1\n",
    "                numcoin[coin] -= 1\n",
    "                change -= coin\n",
    "            \n",
    "    if change != 0:\n",
    "        print(\"釣銭切れ\")\n",
    "    else:\n",
    "        for coin, num in numchange.items():\n",
    "            if num == 0:\n",
    "                continue\n",
    "            else:\n",
    "                print(str(coin) + \"円玉×\" + str(num), end=\", \")\n",
    "                \n",
    "calcchange(coins, numcoin)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下図の有向グラフにおいて、与えられた開始地点xから与えられた最終地点yまでの経路を1つ出力するプログラムを書け。\n",
    "\n",
    "ヒント1. グラフは隣接辞書として表現するとよい。例えば、地点aの隣はbとcとdなので、{'a': {'b','c','d'}, ...}のように表せる。\n",
    "\n",
    "ヒント2. 最短経路の探索関数は再帰関数として定義するとよい。つまり、探索関数をgsとすると、gs(x, y, ...)とし、xは現在いる地点、yはゴール地点とする。gs(x,y,...)は、現在地点x=yなら、ゴールしたので、そこまでの経路を出力して終了。そうでなければ、xの隣の状態wを選びgs(w,y,...)を呼び出す。なお、このグラフには閉路があるのでそのケアも忘れないこと。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', 'b']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def gs(x,y,path):\n",
    "    p = list(path)\n",
    "    p.append(x)\n",
    "    if x == y:\n",
    "        print(p)\n",
    "        return True\n",
    "    else:\n",
    "        if edges[x] == set():\n",
    "            return False\n",
    "        else:\n",
    "            for z in edges[x]:\n",
    "                if z in p:\n",
    "                    return False\n",
    "                else:\n",
    "                    if gs(z,y,p):\n",
    "                        return True\n",
    "    \n",
    "edges = {\n",
    "    'a':{'b', 'c', 'd'},\n",
    "    'b':{'d', 'g'},\n",
    "    'c':{'b', 'e', 'g'},\n",
    "    'd':{'e', 'f'},\n",
    "    'e':{'f', 'g'},\n",
    "    'f':{},\n",
    "    'g':{}\n",
    "}\n",
    "\n",
    "gs('a', 'b', [])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}