main.ipynb

{
  "cells": [
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kWinD8f2Pht6",
        "outputId": "0a22bb38-b443-469f-9eda-63287420c08b"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "True\n",
            "[[0, 0, 1, 3, 3], [[0, 2, 0, 3, 1], [[0, 1, 1, 3, 2], [[0, 3, 0, 3, 0], [[0, 2, 1, 3, 1], [[2, 2, 0, 1, 1], [[1, 1, 1, 2, 2], [[3, 1, 0, 0, 2], [[3, 0, 1, 0, 3], [[3, 2, 0, 0, 1], [[2, 2, 1, 1, 1], [[3, 3, 0, 0, 0], None]]]]]]]]]]]]\n"
          ]
        }
      ],
      "source": [
        "# Giải quyết bài toán người và quỷ qua sông\n",
        "\n",
        "def check(O):\n",
        "  if O[0] == O[1]:\n",
        "    return True\n",
        "  if O[0] == 0 or O[3] ==0:\n",
        "    return True\n",
        "  return False\n",
        "\n",
        "def Children(O):\n",
        "  res = []\n",
        "  # 1 người qua sông\n",
        "  if O[2] == 0:\n",
        "    if O[0]>=1:\n",
        "      child = [O[0]-1,O[1],1,O[3]+1,O[4]]\n",
        "      if check(child):\n",
        "        res.append(child)\n",
        "  else:\n",
        "    if O[3]>=1:\n",
        "      child = [O[0]+1,O[1],0,O[3]-1,O[4]]\n",
        "      if check(child):\n",
        "        res.append(child)\n",
        "  \n",
        "  # 2 người qua sông\n",
        "  if O[2] == 0:\n",
        "    if O[0]>=2:\n",
        "      child = [O[0]-2,O[1],1,O[3]+2,O[4]]\n",
        "      if check(child):\n",
        "        res.append(child)\n",
        "  else:\n",
        "    if O[3]>=2:\n",
        "      child = [O[0]+2,O[1],0,O[3]-2,O[4]]\n",
        "      if check(child):\n",
        "        res.append(child) \n",
        "  # 1 quỷ qua sông\n",
        "  if O[2] == 0:\n",
        "    if O[1]>=1:\n",
        "      child = [O[0],O[1]-1,1,O[3],O[4]+1]\n",
        "      if check(child):\n",
        "        res.append(child)\n",
        "  else:\n",
        "    if O[4]>=1:\n",
        "      child = [O[0],O[1]+1,0,O[3],O[4]-1]\n",
        "      if check(child):\n",
        "        res.append(child)\n",
        "  # 2 quỷ qua sông\n",
        "  if O[2] == 0:\n",
        "    if O[1]>=2:\n",
        "      child = [O[0],O[1]-2,1,O[3],O[4]+2]\n",
        "      if check(child):\n",
        "        res.append(child)\n",
        "  else:\n",
        "    if O[4]>=2:\n",
        "      child = [O[0],O[1]+2,0,O[3],O[4]-2]\n",
        "      if check(child):\n",
        "        res.append(child)\n",
        "  # 1 người 1 quỷ qua sông\n",
        "  if O[2] == 0:\n",
        "    if O[0]>=1 and O[1]>=1:\n",
        "      child = [O[0]-1,O[1]-1,1,O[3]+1,O[4]+1]\n",
        "      if check(child):\n",
        "        res.append(child)\n",
        "  else:\n",
        "    if O[3]>=1 and O[4]>=1:\n",
        "      child = [O[0]+1,O[1]+1,0,O[3]-1,O[4]-1]\n",
        "      if check(child):\n",
        "        res.append(child) \n",
        "  return res\n",
        "\n",
        "# (Người bên trái, quỷ bên trái, vị trí thuyền, NBP, QBP)\n",
        "Start = [3,3,0,0,0]\n",
        "Goal = [0,0,1,3,3]\n",
        "\n",
        "OK = False\n",
        "# Bước 1: Cho đỉnh xuất phát vào open. \n",
        "Open = [[Start,None]]\n",
        "closed = []\n",
        "\n",
        "# Bước 2 - 6: Nếu open rỗng thì tìm kiếm thất bại, kết thúc việc tìm kiếm.\n",
        "while len(Open)>0:\n",
        "  # Bước 3: Lấy đỉnh đầu trong open ra và gọi đó là ʘ. Cho ʘ vào closed\n",
        "  O_totien = Open.pop()\n",
        "  O = O_totien[0]\n",
        "  closed.append(O)\n",
        "  # Bước 4: Nếu ʘ là đỉnh đích thì tìm kiếm thành công, kết thúc việc tìm kiếm.\n",
        "  if O == Goal:\n",
        "    OK = True\n",
        "    break\n",
        "  #Bước 5: Tìm tất cả các đỉnh con của ʘ không thuộc open và closed cho vào cuối của open\n",
        "  for child in Children(O):\n",
        "    if child not in Open and child not in closed:\n",
        "      Open.append([child,O_totien])\n",
        "\n",
        "print(OK)\n",
        "print(O_totien)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {
        "id": "PkmM5gknNHqF"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "(0, 12, 5, 8)\n",
            "(10, 2, 1, 4)\n",
            "(3, 13, 7, 9)\n",
            "(14, 15, 11, 6)\n"
          ]
        },
        {
          "ename": "KeyboardInterrupt",
          "evalue": "",
          "output_type": "error",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
            "Cell \u001b[0;32mIn [9], line 89\u001b[0m\n\u001b[1;32m     87\u001b[0m       h \u001b[39m=\u001b[39m distance(child,Goal)\n\u001b[1;32m     88\u001b[0m       f \u001b[39m=\u001b[39m g\u001b[39m+\u001b[39mh \n\u001b[0;32m---> 89\u001b[0m       Open\u001b[39m.\u001b[39mput(((f,g),child,i,O_totien))\n\u001b[1;32m     90\u001b[0m       closed\u001b[39m.\u001b[39madd(child)\n\u001b[1;32m     92\u001b[0m \u001b[39mprint\u001b[39m(OK,count)\n",
            "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
          ]
        }
      ],
      "source": [
        "import random as rd\n",
        "from queue import PriorityQueue\n",
        "#Trò chơi 8 số\n",
        "\n",
        "def Zero(S):\n",
        "  n = len(S)\n",
        "  for i in range(n):\n",
        "    for j in range(n):\n",
        "      if S[i][j] == 0:\n",
        "        return (i,j)\n",
        "\n",
        "# o = 0 : Up\n",
        "# o = 1 : Down\n",
        "# o = 2 : Left\n",
        "# o = 3 : Right\n",
        "def move(S,o):\n",
        "  n = len(S)\n",
        "  A = [list(_) for _ in S]\n",
        "  i,j = Zero(S)\n",
        "  if o==0:\n",
        "    if i<n-1:\n",
        "      A[i][j] = A[i+1][j]\n",
        "      A[i+1][j] = 0\n",
        "      return tuple([tuple(_) for _ in A])\n",
        "  elif o==1:\n",
        "    if i>0:\n",
        "      A[i][j] = A[i-1][j]\n",
        "      A[i-1][j] = 0\n",
        "      return tuple([tuple(_) for _ in A])\n",
        "  elif o==2:\n",
        "    if j<n-1:\n",
        "      A[i][j] = A[i][j+1]\n",
        "      A[i][j+1] = 0\n",
        "      return tuple([tuple(_) for _ in A])\n",
        "  elif o==3:\n",
        "    if j>0:\n",
        "      A[i][j] = A[i][j-1]\n",
        "      A[i][j-1] = 0\n",
        "      return tuple([tuple(_) for _ in A])\n",
        "  return None\n",
        "\n",
        "\n",
        "def distance(S,G):\n",
        "  ans = 0\n",
        "  n = len(S)\n",
        "  for i in range(n):\n",
        "    for j in range(n):\n",
        "      if S[i][j]!=G[i][j]:\n",
        "        ans +=1\n",
        "  return ans\n",
        "\n",
        "#Goal = ((1,2,3),(4,5,6),(7,8,0))\n",
        "Goal = ((1,2,3,4),(5,6,7,8),(9,10,11,12),(13,14,15,0))\n",
        "Start = Goal\n",
        "for _ in range(2000):\n",
        "  c = move(Start,rd.randint(0,4))\n",
        "  if c!=None:\n",
        "    Start = c\n",
        "\n",
        "for _ in Start: print(_)\n",
        "\n",
        "OK = False\n",
        "# Bước 1: Cho đỉnh xuất phát vào open. \n",
        "Open = PriorityQueue()\n",
        "g = 0\n",
        "h = distance(Start,Goal)\n",
        "f = g+h\n",
        "Open.put(((f,g),Start,None,None))\n",
        "closed = {Start}\n",
        "\n",
        "count = 0\n",
        "# Bước 2 - 6: Nếu open rỗng thì tìm kiếm thất bại, kết thúc việc tìm kiếm.\n",
        "while not Open.empty():\n",
        "  count += 1\n",
        "  # Bước 3: Lấy đỉnh đầu trong open ra và gọi đó là ʘ. Cho ʘ vào closed\n",
        "  O_totien = Open.get()\n",
        "  O = O_totien[1]\n",
        "  # Bước 4: Nếu ʘ là đỉnh đích thì tìm kiếm thành công, kết thúc việc tìm kiếm.\n",
        "  if O == Goal:\n",
        "    OK = True\n",
        "    break\n",
        "  #Bước 5: Tìm tất cả các đỉnh con của ʘ không thuộc open và closed cho vào cuối của open\n",
        "  for i in range(4):\n",
        "    child = move(O,i)\n",
        "    if child!=None and child not in closed:\n",
        "      g = O_totien[0][1] + 1\n",
        "      h = distance(child,Goal)\n",
        "      f = g+h \n",
        "      Open.put(((f,g),child,i,O_totien))\n",
        "      closed.add(child)\n",
        "\n",
        "print(OK,count)\n",
        "\n",
        "def Myprint(S):\n",
        "  if S[3]!=None:\n",
        "    Myprint(S[3])\n",
        "    print(S[2])\n",
        "  for _ in S[1]: print(_)\n",
        "\n",
        "Myprint(O_totien)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "qy2m__2zz61l"
      },
      "outputs": [],
      "source": [
        "# Hãy viết chương trình trò chơi Tic-Tac-Toe\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "EvYB376W0CO_",
        "outputId": "7e2503fe-d53e-4a72-f47c-8bdbbf7fce10"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "+ 0 1 2 3 4 5 6 7 +\n",
            "0 _ _ _ _ _ _ \u001b[34mB\u001b[0m _ 0\n",
            "1 _ \u001b[34mN\u001b[0m _ _ _ _ _ _ 1\n",
            "2 _ \u001b[34mP\u001b[0m \u001b[34mK\u001b[0m _ _ _ _ _ 2\n",
            "3 _ _ _ \u001b[31mk\u001b[0m _ _ _ _ 3\n",
            "4 _ _ _ _ _ _ _ _ 4\n",
            "5 _ _ _ \u001b[31mp\u001b[0m _ _ _ _ 5\n",
            "6 _ \u001b[34mB\u001b[0m _ \u001b[31mr\u001b[0m _ _ _ _ 6\n",
            "7 _ _ _ _ _ _ _ _ 7\n",
            "+ 0 1 2 3 4 5 6 7 +\n",
            "\n",
            "---- True turn ----\n",
            "3 3 2 2\n",
            "+ 0 1 2 3 4 5 6 7 +\n",
            "0 _ _ _ _ _ _ \u001b[34mB\u001b[0m _ 0\n",
            "1 _ \u001b[34mN\u001b[0m _ _ _ _ _ _ 1\n",
            "2 _ \u001b[34mP\u001b[0m \u001b[31mk\u001b[0m _ _ _ _ _ 2\n",
            "3 _ _ _ _ _ _ _ _ 3\n",
            "4 _ _ _ _ _ _ _ _ 4\n",
            "5 _ _ _ \u001b[31mp\u001b[0m _ _ _ _ 5\n",
            "6 _ \u001b[34mB\u001b[0m _ \u001b[31mr\u001b[0m _ _ _ _ 6\n",
            "7 _ _ _ _ _ _ _ _ 7\n",
            "+ 0 1 2 3 4 5 6 7 +\n",
            "\n",
            "Random Won\n"
          ]
        }
      ],
      "source": [
        "# cờ vua\n",
        "import random\n",
        "from termcolor import colored\n",
        "from IPython.display import clear_output\n",
        "import time\n",
        "# K, k: Vua\n",
        "# Q, q: Hậu\n",
        "# R, r: Xe\n",
        "# B, b: Tượng\n",
        "# N, n: Mã\n",
        "# P, p: Tốt\n",
        "liR = [(1,0),(2,0),(3,0),(4,0),(5,0),(6,0),(7,0)]\n",
        "liL = [(-1,0),(-2,0),(-3,0),(-4,0),(-5,0),(-6,0),(-7,0)]\n",
        "liD = [(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7)]\n",
        "liU = [(0,-1),(0,-2),(0,-3),(0,-4),(0,-5),(0,-6),(0,-7)]\n",
        "liRD = [(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)]\n",
        "liLU = [(-1,-1),(-2,-2),(-3,-3),(-4,-4),(-5,-5),(-6,-6),(-7,-7)]\n",
        "liRU = [(1,-1),(2,-2),(3,-3),(4,-4),(5,-5),(6,-6),(7,-7)]\n",
        "liLD = [(-1,1),(-2,2),(-3,3),(-4,4),(-5,5),(-6,6),(-7,7)]\n",
        "liN = [(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1)]\n",
        "liK = [(0,1),(1,0),(0,-1),(-1,0),(1,1),(-1,1),(1,-1),(-1,-1)]\n",
        "\n",
        "board = [['r','n','b','q','k','b','n','r'],\n",
        "         ['p','p','p','p','p','p','p','p'],\n",
        "         ['_','_','_','_','_','_','_','_'],\n",
        "         ['_','_','_','_','_','_','_','_'],\n",
        "         ['_','_','_','_','_','_','_','_'],\n",
        "         ['_','_','_','_','_','_','_','_'],\n",
        "         ['P','P','P','P','P','P','P','P'],\n",
        "         ['R','N','B','Q','K','B','N','R']]\n",
        "\n",
        "# kiểm tra có thể đi được hay không (Xe, Tượng, Hậu)\n",
        "def Go(x,y,l,isContinue=False,canFight=True,needFight=False):\n",
        "  li = []\n",
        "  for dx,dy in l:\n",
        "    x1 = x+dx\n",
        "    y1 = y+dy\n",
        "    if x1<0 or x1>=8 or y1<0 or y1>=8: \n",
        "      if not isContinue: \n",
        "        break \n",
        "      else: \n",
        "        continue\n",
        "    if board[y1][x1] != '_':\n",
        "      if canFight and board[y][x].islower() != board[y1][x1].islower():\n",
        "        li.append((x1,y1))\n",
        "      if not isContinue: break \n",
        "      else: continue\n",
        "    if not needFight:\n",
        "      li.append((x1,y1))\n",
        "  return li\n",
        "\n",
        "\n",
        "# các nước có thể đi của quân Xe\n",
        "def Rr(x,y):\n",
        "  return Go(x,y,liR) + Go(x,y,liL) + Go(x,y,liU) + Go(x,y,liD)\n",
        "\n",
        "# các nước có thể đi của quân Tượng\n",
        "def Bb(x,y):\n",
        "  return Go(x,y,liRD) + Go(x,y,liLU) + Go(x,y,liRU) + Go(x,y,liLD)\n",
        "\n",
        "# các nước có thể đi của quân Hậu\n",
        "def Qq(x,y):\n",
        "  return Rr(x,y) + Bb(x,y)\n",
        "\n",
        "# các nước có thể đi của quân Mã\n",
        "def Nn(x,y):\n",
        "  return Go(x,y,liN,isContinue=True)\n",
        "\n",
        "# các nước có thể đi của quân Vua\n",
        "def Kk(x,y):\n",
        "  return Go(x,y,liK,isContinue=True)\n",
        "\n",
        "# các nước có thể đi của quân Tốt\n",
        "def Pp(x,y):\n",
        "  li = []\n",
        "  dx = 1\n",
        "  if not board[y][x].islower():\n",
        "    dx = -1\n",
        "  # nước có thể đi\n",
        "  if y==1 or y==6:\n",
        "    li = li + Go(x,y,[(0,dx),(0,2*dx)],canFight=False)\n",
        "  else:\n",
        "    li = li + Go(x,y,[(0,dx)], canFight=False)\n",
        "  # nước có thể ăn (tốt ăn chéo)\n",
        "  li = li + Go(x,y,[(-1,dx),(1,dx)],needFight=True)\n",
        "  return li\n",
        "\n",
        "# x, y là tọa độ quân cờ\n",
        "# islower lượt của quân thường (True) hay quân hoa (False)\n",
        "# return danh sách tọa độ các nước có thể di chuyển tới\n",
        "def CanGo(x,y,islower):\n",
        "  if board[y][x].islower() != islower:\n",
        "    return []\n",
        "  if (board[y][x] in \"Rr\"):\n",
        "    return Rr(x,y)\n",
        "  if (board[y][x] in \"Nn\"):\n",
        "   return Nn(x,y)\n",
        "  if (board[y][x] in \"Bb\"):\n",
        "    return Bb(x,y)\n",
        "  if (board[y][x] in \"Qq\"):\n",
        "    return Qq(x,y)\n",
        "  if (board[y][x] in \"Kk\"):\n",
        "    return Kk(x,y)\n",
        "  if (board[y][x] in \"Pp\"):\n",
        "    return Pp(x,y)\n",
        "  return []\n",
        "\n",
        "\n",
        "def isFinish(board):\n",
        "  U = False\n",
        "  L = False\n",
        "  for _ in board:\n",
        "    U = U or ('K' in _)\n",
        "    L = L or ('k' in _)\n",
        "  return not (U and L)\n",
        "\n",
        "# return tất cả các nước có thể di chuyển (y,x) -> (y1,x1)\n",
        "def CanGoList(board,islower):\n",
        "  li = []\n",
        "  for y in range(8):\n",
        "    for x in range(8):\n",
        "      l = CanGo(x,y,islower)\n",
        "      for x1,y1 in l:\n",
        "        li = li + [(y,x,y1,x1)]\n",
        "  return li\n",
        "\n",
        "def CPURandomTurn(board,islower):\n",
        "  #######################################################\n",
        "  #  Có thể bỏ time.sleep(1) để xem kết quả nhanh hơn   #\n",
        "  ####################################################### \n",
        "  #time.sleep(1)\n",
        "  li = CanGoList(board,islower)\n",
        "  return random.choice(li)\n",
        "\n",
        "def CPUMiniMaxTurn(board,islower,depth = 2):\n",
        "  #######################################################\n",
        "  #  Nên dùng Minimax với độ sâu từ 2 đến 4             #\n",
        "  #######################################################\n",
        "  li = CanGoList(board,islower)\n",
        "  Max = -1000\n",
        "  for y,x,y1,x1 in CanGoList(board,islower):\n",
        "    child = [_[:] for _ in board]\n",
        "    child[y1][x1] = child[y][x]\n",
        "    child[y][x] = '_'\n",
        "    vl = Minimax(child,depth-1,islower,not islower)\n",
        "    if Max < vl or (Max == vl and random.choice([0,1])==0):\n",
        "      Max = vl\n",
        "      r = (y,x,y1,x1)\n",
        "  return r\n",
        "\n",
        "# Board: Bàn cờ hiện tại\n",
        "# islower: lượt của quân viết thường (True) hay quân viết hoa (False)\n",
        "# return: giá trị của bàn cờ đối với quân viết thường\n",
        "def value(board,islower):\n",
        "  vl = 0\n",
        "  ######################################################\n",
        "  #  Cần định nghĩa lại hàm value                      #\n",
        "  #  Gợi ý:                                            #\n",
        "  #       1. Hiệu số quân cờ 2 bên                     #\n",
        "  #       2. Vị trí quân cờ trên bàn cờ                #\n",
        "  #       3. Tùy suy nghĩ của các em                   #\n",
        "  ######################################################\n",
        "  return vl\n",
        "\n",
        "# node là node hiện tại\n",
        "# depth là độ sâu\n",
        "# Pmax là player cần tìm Max\n",
        "# Pnow là player hiện tại\n",
        "def Minimax(node,depth,Pmax,Pnow):\n",
        "  if isFinish(node) or depth ==0:\n",
        "    return value(node,Pmax)\n",
        "  if Pmax == Pnow:\n",
        "    Max = -1000\n",
        "    for y,x,y1,x1 in CanGoList(node,Pnow):\n",
        "      child = [_[:] for _ in node]\n",
        "      child[y1][x1] = child[y][x]\n",
        "      child[y][x] = '_'\n",
        "      Max = max(Max,Minimax(child,depth-1,Pmax,not Pnow))\n",
        "    return Max\n",
        "  else:\n",
        "    Min = 1000\n",
        "    for y,x,y1,x1 in CanGoList(node,Pnow):\n",
        "      child = [_[:] for _ in node]\n",
        "      child[y1][x1] = child[y][x]\n",
        "      child[y][x] = '_'\n",
        "      Min = min(Min,Minimax(child,depth-1,Pmax,not Pnow))\n",
        "    return Min\n",
        "\n",
        "\n",
        "def printBoard(board):\n",
        "  print(\"+\",*range(8),\"+\")\n",
        "\n",
        "  for i in range(8):\n",
        "    print(i,end=\" \")\n",
        "    for j in range(8):\n",
        "      if board[i][j] == '_':\n",
        "        print(board[i][j],end=\" \")\n",
        "      elif board[i][j].islower():\n",
        "        print(colored(board[i][j],'red'),end=\" \")\n",
        "      else:\n",
        "        print(colored(board[i][j],'blue'),end=\" \")\n",
        "    print(i,) \n",
        "\n",
        "  print(\"+\",*range(8),\"+\")\n",
        "  print()\n",
        "\n",
        "Random = True\n",
        "MiniMax = False\n",
        "Now = Random\n",
        "\n",
        "while not isFinish(board):\n",
        "  clear_output()\n",
        "  printBoard(board)\n",
        "  print(\"----\",Now,\"turn\",\"----\")\n",
        "  if Now == MiniMax:\n",
        "    y,x,y1,x1 = CPUMiniMaxTurn(board,MiniMax)\n",
        "    board[y1][x1] = board[y][x]\n",
        "    board[y][x] = '_'\n",
        "    Now = Random\n",
        "    print(y,x,y1,x1)\n",
        "  else:\n",
        "    y,x,y1,x1 = CPURandomTurn(board,Random)\n",
        "    board[y1][x1] = board[y][x]\n",
        "    board[y][x] = '_'\n",
        "    print(y,x,y1,x1)\n",
        "    Now = MiniMax\n",
        "\n",
        "printBoard(board)\n",
        "if Now:\n",
        "  print(\"Minimax Won\")\n",
        "else:\n",
        "  print(\"Random Won\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3lVsmFXpbGOr",
        "outputId": "3920b346-8422-411c-d503-f867d9480272"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Tao,Cherry,DaoTien,Chuoi,Le,CaChua,CaTim,Toi,PhoMai,469,10\n",
            "Tao,Cherry,DaoTien,Chuoi,Le,CaChua,CaTim,Toi,PhoMai,469,10\n",
            "Tao,Cherry,DaoTien,Chuoi,Le,CaChua,CaTim,Toi,PhoMai,469,10\n",
            "Thom,SuaBo,CaChua,CaRot,CaTim,Bo,373,10\n",
            "Thom,SuaBo,CaChua,CaRot,CaTim,Bo,373,10\n",
            "Thom,SuaBo,CaChua,CaRot,CaTim,Bo,373,10\n",
            "Duahau,Chanh,Nho,DaoTien,Thom,CaTim,HanhTay,BanhMy,Ca,Bo,459,10\n",
            "Cherry,Chanh,Kiwi,CaTim,HanhTay,BanhMy,Cua,Ca,456,10\n",
            "Duahau,DaoTien,Thom,KhoaiTay,PhoMai,211,9\n",
            "Cherry,DuaLuoi,CaChua,HanhTay,KhoaiTay,BanhMy,Cua,371,9\n",
            "Le,Tom,Trung,177,7\n",
            "Tao,Cherry,Nho,Thom,BanhMy,Cua,269,9\n",
            "Tao,Quyt,Nho,Thom,Le,CaTim,Ngheu,274,8\n",
            "Quyt,Chanh,Nho,Thom,CaTim,HanhTay,BanhMy,314,10\n",
            "Le,CaTim,KhoaiTay,Nam,PhoMai,Ngheu,237,9\n",
            "Le,CaTim,KhoaiTay,Nam,PhoMai,Ngheu,237,9\n",
            "Le,CaTim,KhoaiTay,Nam,PhoMai,Ngheu,237,9\n",
            "Chanh,Thom,BanhMy,Cua,184,9\n",
            "Chanh,Thom,BanhMy,Cua,184,9\n",
            "Chanh,Thom,BanhMy,Cua,184,9\n",
            "Le,CaTim,KhoaiTay,PhoMai,123,7\n",
            "Chanh,KhoaiTay,BanhMy,Cua,183,8\n",
            "Duahau,Chanh,Cua,133,8\n",
            "Duahau,Chanh,Le,PhoMai,160,9\n",
            "Chanh,Thom,Le,CaTim,Cua,160,9\n",
            "Duahau,Chanh,Le,PhoMai,160,9\n",
            "CaTim,KhoaiTay,PhoMai,110,7\n",
            "Chanh,Nho,CaTim,BanhMy,155,8\n",
            "Chanh,Thom,CaTim,Tom,Bo,232,10\n",
            "Chanh,CaTim,BanhMy,PhoMai,180,9\n",
            "Chanh,CaTim,Nam,PhoMai,168,9\n",
            "Chanh,Thom,CaTim,Nam,PhoMai,201,10\n",
            "Chanh,Thom,Le,CaTim,PhoMai,174,10\n",
            "Chanh,Thom,Le,CaTim,PhoMai,174,10\n",
            "Chanh,Thom,Le,CaTim,PhoMai,174,10\n",
            "Chanh,Thom,Le,CaTim,PhoMai,174,10\n",
            "Chanh,Thom,Le,CaTim,PhoMai,174,10\n",
            "Chanh,Thom,Le,CaTim,PhoMai,174,10\n",
            "Chanh,Thom,Le,CaTim,PhoMai,174,10\n",
            "Chanh,Thom,Le,CaTim,PhoMai,174,10\n",
            "Chanh,Le,CaTim,PhoMai,141,9\n",
            "Chanh,Le,CaTim,PhoMai,141,9\n",
            "Chanh,Le,CaTim,PhoMai,141,9\n",
            "Chanh,Le,CaTim,PhoMai,141,9\n",
            "Chanh,Le,CaTim,PhoMai,141,9\n",
            "Chanh,Le,CaTim,PhoMai,141,9\n",
            "Chanh,Le,CaTim,PhoMai,141,9\n",
            "Chanh,Le,CaTim,PhoMai,141,9\n",
            "Chanh,Thom,CaTim,KhoaiTay,PhoMai,193,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n",
            "Chanh,Thom,CaTim,PhoMai,161,10\n"
          ]
        }
      ],
      "source": [
        "import random as rd\n",
        "# Bài toán tìm tổ hợp các món ăn sao cho đủ hết các chất dinh dưỡng và giá tiền nhỏ nhất\n",
        "FoodName=[\"Tao\",\"Cherry\",\"Cam\",\"Quyt\",\"Duahau\",\"Chanh\",\"Kiwi\",\"Nho\",\n",
        "\t\t\t\t\t\t\"DuaLuoi\",\"DaoTien\",\"Chuoi\",\"DauTay\",\"Thom\",\"Le\",\"SuaBo\",\"CaChua\",\n",
        "\t\t\t\t\t\t\"CaRot\",\"CaTim\",\"HanhTay\",\"Toi\",\"KhoaiTay\",\"Nam\",\"BanhMy\",\"PhoMai\",\n",
        "\t\t\t\t\t\t\"Bia\",\"Ngheu\",\"Cua\",\"Ca\",\"Tom\",\"Ga\",\"Bo\",\"Trung\"]\n",
        "Food=[[0,0,1,1,0,0,0,0,0,0],[0,0,1,0,0,0,1,1,0,0],[0,0,1,0,0,0,0,0,1,1],[0,0,1,1,1,0,0,0,0,1],\n",
        "\t\t\t[0,0,1,0,0,0,0,1,0,0],[0,0,0,1,0,0,1,0,0,1],[0,0,1,1,1,0,0,1,0,1],[0,0,1,0,0,1,0,0,0,0],\n",
        "\t\t\t[0,0,0,0,0,1,1,0,1,0],[0,0,1,1,0,1,0,0,0,0],[0,0,1,0,0,1,0,0,0,1],[0,0,1,1,0,0,1,0,0,1],\n",
        "\t\t\t[0,0,1,0,0,0,0,0,1,0],[0,0,1,0,0,0,0,0,0,0],[1,1,1,0,1,1,0,1,0,0],[0,0,1,0,0,1,0,1,0,1],\n",
        "\t\t\t[0,0,1,1,0,0,1,1,0,0],[0,0,0,0,0,0,0,1,0,0],[0,0,1,0,1,1,0,0,0,0],[1,0,0,1,0,0,1,0,1,1],\n",
        "\t\t\t[0,0,1,0,0,0,0,0,0,1],[0,0,1,1,0,0,0,0,0,0],[1,1,1,0,0,0,0,0,0,0],[1,1,0,0,1,1,0,0,0,0],\n",
        "\t\t\t[0,0,1,0,0,0,0,0,0,0],[1,0,0,0,1,1,0,0,1,0],[1,0,0,0,1,1,0,0,0,0],[1,1,0,0,0,0,0,0,1,0],\n",
        "\t\t\t[1,0,0,0,1,0,1,0,0,0],[1,0,0,0,0,1,0,1,0,0],[1,1,0,0,0,1,0,0,0,0],[1,1,0,0,1,1,0,1,0,0]]\n",
        "FoodValue=[31,66,55,70,34,50,106,38,\n",
        "\t\t\t62,49,55,82,33,13,118,54,\n",
        "\t\t\t83,15,56,123,32,40,52,63,\n",
        "\t\t\t18,74,49,62,64,55,70,100]\n",
        "\n",
        "def KhoiTao():\n",
        "  global ng,f,n\n",
        "  ng = [[rd.randint(0,1) for __ in range(32)] for _ in range(n)]\n",
        "\n",
        "def DanhGia():\n",
        "  global ng,f,n\n",
        "  f = [None]*n\n",
        "  for j in range(n):\n",
        "    g = ng[j]\n",
        "    tien = 0\n",
        "    for i in range(32):\n",
        "      tien += FoodValue[i]*g[i]\n",
        "   \n",
        "    dinhduong = 0\n",
        "    for k in range(10):\n",
        "      co = 0\n",
        "      for i in range(32):\n",
        "        if g[i] == 1 and Food[i][k] == 1:\n",
        "          co = 1\n",
        "      dinhduong += co\n",
        "    f[j] = tien - 50*dinhduong\n",
        "\n",
        "def PrintBest():\n",
        "  global ng,f,n\n",
        "  fc = [_ for _ in f]\n",
        "  fc.sort()\n",
        "  best = fc[0]\n",
        "  for j in range(n):\n",
        "    if f[j]==best:\n",
        "      tien = 0\n",
        "      for i in range(32):\n",
        "        if ng[j][i] == 1:\n",
        "          tien += FoodValue[i]\n",
        "          print(FoodName[i],end=\",\")\n",
        "      print(tien,end=\",\")\n",
        "      dinhduong = 0\n",
        "      for k in range(10):\n",
        "        co = 0\n",
        "        for i in range(32):\n",
        "          if ng[j][i] == 1 and Food[i][k] == 1:\n",
        "            co = 1\n",
        "        dinhduong += co\n",
        "      print(dinhduong)\n",
        "      break\n",
        "\n",
        "def LuaChon():\n",
        "  global ng,f,n\n",
        "  fc = [_ for _ in f]\n",
        "  fc.sort()\n",
        "  nguong = fc[80*n//100]\n",
        "  for i in range(n):\n",
        "    if f[i]>nguong:\n",
        "      ng[i] = [_ for _ in ng[rd.randrange(0,n)]]\n",
        "\n",
        "def LaiGhep():\n",
        "  global ng,f,n\n",
        "  for _ in range(n*30//100):\n",
        "    cha = rd.randrange(0,n)\n",
        "    me = rd.randrange(0,n)\n",
        "    for i in range(32):\n",
        "      if rd.randint(0,1)==0:\n",
        "        ng[cha][i],ng[me][i] = ng[me][i],ng[cha][i]\n",
        "\n",
        "def DotBien():\n",
        "  global ng,f,n\n",
        "  dt = rd.randrange(0,n)\n",
        "  k = rd.randrange(0,32)\n",
        "  ng[dt][k] = 1-ng[dt][k]\n",
        "\n",
        "n = 100\n",
        "KhoiTao()\n",
        "for _ in range(100):\n",
        "  DanhGia()\n",
        "  PrintBest()\n",
        "  LuaChon()\n",
        "  LaiGhep()\n",
        "  DotBien()\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "background_save": true
        },
        "id": "Jj4eTNlLoJlN",
        "outputId": "759eaba1-ceff-492e-c108-9bb2568a6a14"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0 37082.13328745022\n",
            "10 30172.059915914975\n",
            "20 27816.620206830437\n",
            "30 29207.822486932\n",
            "40 29207.822486932\n",
            "50 29317.23536468914\n",
            "60 28401.860985700703\n",
            "70 27816.620206830437\n",
            "80 27816.620206830437\n",
            "90 28401.860985700703\n",
            "100 27816.620206830437\n",
            "110 27816.620206830437\n",
            "120 27816.620206830437\n",
            "130 27816.620206830437\n",
            "140 27816.620206830437\n",
            "150 27816.620206830437\n",
            "160 27816.620206830434\n",
            "170 27816.620206830437\n",
            "180 27816.620206830434\n",
            "190 27816.620206830434\n",
            "200 27816.620206830434\n",
            "210 27816.620206830437\n",
            "220 27816.620206830437\n",
            "230 27816.620206830437\n",
            "240 27816.620206830437\n",
            "250 27816.620206830437\n",
            "260 27816.620206830437\n",
            "270 27816.620206830437\n",
            "280 27816.620206830437\n",
            "290 27816.620206830437\n",
            "300 27816.620206830437\n",
            "310 27816.620206830437\n",
            "320 27816.620206830437\n",
            "330 27816.620206830437\n",
            "340 27816.620206830437\n",
            "350 27816.620206830437\n",
            "360 27816.620206830437\n",
            "370 27816.620206830437\n",
            "380 27816.620206830437\n",
            "390 27816.620206830437\n",
            "400 27816.620206830437\n",
            "410 27816.620206830437\n",
            "420 27816.620206830437\n",
            "430 27816.620206830437\n",
            "440 27816.620206830437\n",
            "450 27816.620206830437\n",
            "460 27816.620206830437\n",
            "470 27816.620206830437\n",
            "480 27816.620206830437\n",
            "490 27816.620206830437\n",
            "500 27816.620206830437\n",
            "510 27816.620206830437\n",
            "520 27816.620206830437\n",
            "530 27816.620206830437\n",
            "540 27816.620206830437\n",
            "550 27816.620206830437\n",
            "560 27816.620206830437\n",
            "570 27816.620206830437\n",
            "580 27816.620206830437\n",
            "590 27816.620206830437\n",
            "600 27816.620206830437\n",
            "610 27816.620206830437\n",
            "620 27816.620206830437\n",
            "630 27816.620206830437\n",
            "640 27816.620206830437\n",
            "650 27816.620206830437\n",
            "660 27816.620206830437\n",
            "670 27816.620206830437\n",
            "680 27816.620206830437\n",
            "690 27816.620206830437\n",
            "700 27816.620206830437\n",
            "710 27816.620206830437\n",
            "720 27816.620206830437\n",
            "730 27816.620206830437\n",
            "740 27816.620206830437\n",
            "750 27816.620206830437\n",
            "760 27816.620206830437\n",
            "770 27816.620206830437\n",
            "780 27816.620206830437\n",
            "790 27816.620206830437\n",
            "800 28401.860985700703\n",
            "810 27816.620206830437\n",
            "820 27816.620206830437\n",
            "830 28401.860985700703\n",
            "840 28401.860985700703\n",
            "850 27816.620206830437\n",
            "860 27816.620206830437\n",
            "870 27816.620206830437\n",
            "880 28401.860985700703\n",
            "890 28401.860985700703\n",
            "900 27816.620206830437\n",
            "910 27816.620206830437\n",
            "920 27816.620206830437\n",
            "930 27816.620206830437\n",
            "940 28401.860985700703\n",
            "950 28401.860985700703\n",
            "960 28401.860985700703\n",
            "970 28401.860985700703\n",
            "980 28401.860985700703\n",
            "990 27816.620206830437\n"
          ]
        },
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAD4CAYAAAAAczaOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3deXxU1dnA8d/Jvu97gIRAICRCZA+yVEUQFYu1ghuKW9G6VMUq2lp9pfqKe21tXYpa6gaIWhFFFkEFZUcCJAQS9i072dfJnPePuYkpL0jASWa5z/fzyYc7d27uPMNMnjlz7nPOUVprhBBCmIOHowMQQgjRdSTpCyGEiUjSF0IIE5GkL4QQJiJJXwghTMTL0QH8lKioKJ2cnOzoMIQQwqVs3ry5VGsdfbL7nDrpJycns2nTJkeHIYQQLkUpdeBU90n3jhBCmIgkfSGEMBFJ+kIIYSKS9IUQwkQk6QshhIlI0hdCCBORpC+EECYiSV8IF1FW08jb3+3jWGW9o0MRLsypB2cJIaC+qYU31+zltW/2UtNo4aXlu3liUgZXnJuIUsrR4QkXIy19IZyUpcXKvA0H+cVzq3h+2W5G9Irk37cMo09sMPfPz+a3726hrKbR0WEKFyMtfSGcjNaaFTuLeebLPAqKaxjUI4y/Xz+IockRAIzsHcWc1Xt5YdluLv7Lt/zvr/ozPiPOwVELV6GcebnEIUOGaJl7R5jJloPHefqLnWzcf5yUqEAempDGxRmxJ+3G2VVYzYwFW8k5WsWVgxJ5/PIMQv29HRC1cDZKqc1a6yEnu09a+kI4gb0lNTy3dBdLdhQSFeTLk1ecw9VDu+Pteeoe2L5xwXxy50heWZnP37/ew9o9ZTx3VSajUqO6MHLhaqSlL4QDlVQ38vJXu/lgwyF8vTyYPiaF34xOIdD3zNpj2YcqmLFgK3tKarlxRBIPX5JGgI+06cxKWvpCOJnaRgv/XL2XN77dS5PFynXDevC7salEB/ue1fkyu4fx+e9G8+yXu3jru318u7uEF6acy+CkcDtHLlydtPSF6ELNLVbmbTzEyyvyKa1p5NL+cTx4cRo9owLt9hhr95Tx4MJsjlbUc/svenHfRan4enna7fzC+f1US1+SvhBdQGvN0pxCnv1yF3tLaxmWHMHDl6YxqEfntMRrGi08uTiXeRsPkRYXzAtTMslICO2UxxLOR5K+EA60cX85T3+xky0HK0iNCWLmhDTG9ovpkoFVK/OKmPnRdirqmrh3bCp3/KIXXj9xcVi4B0n6QjhAQXE1s5fsYsXOImJDfJkxrg+/HtSty5Pu8domHluUw2fZR8nsHsaLUzLpFR3UpTGIriVJX4guVFTVwF9W7Gb+xkME+Hjx2/N7ccvInvj7OLZfffG2ozz6nx3UN7Uwc0IaN52XjIeHTOPgjqR6R4guUN3QzOvf7GXOmr20WDU3jkjmngt7Exl0dhU59jZxQILtWsLH25m1OJfluUU8N3kA3cIDHB2a6ELS0hfiZ2qyWHl//QH+urKA8tomLs9M4MHxfekR6ZzJVGvNh5sO88RnOSileGxiOpOHdJPJ29yItPSF6ARaaxZvO8bzy3ZxoKyOESmRPHJpGgO6hTk6tJ+klGLK0O6M6BXJgwuzeeijbSzNKeTpX/cnJtjP0eGJTiYtfSHOwvd7Spm9JI9thytJiwtm5iVpnN8n2uVay1ar5l/f7+eZL/Pw9/HkySvOYeKABEeHJX4maekLYSd5hVU8sySPVbtKSAj14/nJmfxqYCKeLnpB1MNDccuonozpE80DH2Zz9/s/sDSniD9PyiAswMfR4YlOIElfiA44WlHPi8t389GWwwT5evHIJWlMOy8ZP2/3GOnaOyaIj+4YwWvf7OEvK/JZv7eMZ349gAvSYhwdmrAz6d4R4hQsLVY27j/OlzuOMW/jIbSGaeclcdcFvd26FZxztJIZ87PZVVTNtcO688fL0gk6wwnghGNJ944QHVTXZOHb3aUsyy1kZV4xFXXN+Hh5MLF/PPeP60P3COesyLGnjIRQFt0zkpeW5/PGt3tYnV/K85MzyUqJdHRowg6kpS9Mr7SmkZU7i1mWW8jq/FIaLVZC/LwY2y+WcemxjOkTbdqW7uYD5TywIJsD5XXcMrInD17c1226tNyZjMgV4gT7S2tZnlvEstxCNh04jtaQEOrH+Iw4xqXHMqxnxE8uYGImdU0WZi/J499rD9ArOpAXp5xLZnfnLks1O0n6wvSsVs32I5Usyy1keW4Ru4tqAOgXH8K49FjGp8eSkRDiciWXXWl1fgkPLdxGcXUjd53fi3vGpsoHo5OSpC9MqcliZd3esrZEX1TViKeHYmhyOOPTbS16M/TR21NlfTNPfJbDx1uOkJEQwotTzqVvXLCjwxInkKQvTKOqoZmvd5WwPLeIr/OKqW604O/tyZg+UYxPj+PCtBjCA9238qarLM0p5A8fb6e6wcID4/tw2+gUlx2r4I6keke4tcLKBpbvLGJZTiHr9pbR3KKJDPTh0v7xjEuPZVRqlFx8tLOLM+IYnBTOHz/ZztNL8lixs4jnJ2eSFGm/FcBE55CWvnA5Wmvyi2tsF2JzCsk+XAlAcmQA4zPiGJ8ey8Ae4dLy7AJaa/6z9QiPfZqDpUXzh8v6MXV4D7k24mDSvSNcXotVs+XgcZbl2Prn95fVAbYFwccbF2J7xwRJsnGQY5X1PLRwG6vzSxmdGsWzVw0gPtTf0WGZliR94ZIamltYk28bKPXVzmLKapvw9lSM6BXF+HRbDX1siMwK6Sy01ry3/iBPfb4TL0/FrEkZXHFuonwQO4D06QuXcby2ia/yilmeW8i3u0upb24h2NeLC9JiGJcey/l9own283Z0mOIklFJMzUpidGoUDyzI5v752SzdUcRTvzrHaRaSEdLSF07gUHkdy3KLWJ5byMb9x2mxauJC/BhntOazUiLx8ZJ6cFfSYtXMWb2XF5btJtjPi/+9sj8XZ8Q5OizT+NndO0qp+4HbAA1sB24G4oF5QCSwGbhBa92klPIF/g0MBsqAq7XW+43zPALcCrQAv9NaL/2px5Wk75601uQcrWKZcSE2r7AagL6xwbaBUhmx9E8MlW4BN7CrsJoZC7aSc7SKKwcl8vjlGYT6yze1zvazkr5SKhFYA6RrreuVUguAL4BLgY+11vOUUq8B2VrrV5VSdwIDtNZ3KKWuAX6ltb5aKZUOfAAMAxKAFUAfrXXLqR5bkr77aG6xsmFfOctzi1ieW8SRino8FAxJimB8hq1FL+V+7qnJYuWVlfn8/es9xAT78txVmYxKjXJ0WG7NHn36XoC/UqoZCACOARcC1xn3zwX+B3gVmGRsAywEXlG2JtskYJ7WuhHYp5QqwPYBsPZMn5BwDTWNFr7dXcKyHNuMlVUNFny9PBidGs29F6UyNi1G+npNwMfLgxnj+zK2XywzFmxl6pvruXFEEg9fkkaAj1xW7Gqn/R/XWh9RSj0PHATqgWXYunMqtNYW47DDQKKxnQgcMn7XopSqxNYFlAisa3fq9r/TRik1HZgO0KNHj7N4SsKRiqsb+GpnMctyCvluTxlNFivhAd5tE5mNTo2SP3STyuwexue/G81zS3fx1nf7+HZ3CS9MyWRwUoSjQzOV0/71KaXCsbXSewIVwIfAhM4KSGv9BvAG2Lp3OutxhP3sKalhWY7tQuwPhyrQGrpH+HNDVhLj02MZnBSOl0zMJQA/b0/+NDGdcemx/P7DbCa/tpbpY3px/7hUfL1k1HRX6EiT6yJgn9a6BEAp9TEwEghTSnkZrf1uwBHj+CNAd+CwUsoLCMV2Qbd1f6v2vyNciNWq2Xq4gmU5tqmJ95bUAtA/MZT7L+rD+IxY+sYGy4VYcUpZKZF8ed8Ynvo8l9e+2cOqvGJevDqTjIRQR4fm9jqS9A8CWUqpAGzdO2OBTcAq4CpsFTzTgE+N4xcZt9ca96/UWmul1CLgfaXUi9gu5KYCG+z4XEQnamhuYe2eMpblFrFiZxEl1Y14eSiyUiK56bxkLuoXS0KYjMAUHRfk68XTVw5gfHocMz/axqRXvuPesan89vxe8s2wE3W0ZPMJ4GrAAvyArXwzEVvCjzD2TdVaNyql/IB3gIFAOXCN1nqvcZ4/ArcY57lPa73kpx5Xqnccq7KumVW7bCtKfbOrhNqmFgJ9PDm/bwzjM2I5v2+MlN8Juzhe28Rji3L4LPsomd3DeGFyJr1jghwdlsuSaRhEhx2tqG9bUWr93nIsVk10sG/bQKnzekVK36voNIu3HeXR/+ygvqmFmRPSuOm8ZDxk4rwzJtMwiFPSWpNXWG27ELuzkB1HqgDoHRPEb8akMD49lsxuYfKHJ7rExAEJDEuO4OGPtzNrcS7Lc4t4bvIAuoXLYjf2Ii19E7K0WNl04Hhboj9UXo9SMKhHeNtEZinR8tVaOI7Wmg83HWbW4lwA/jSxH1OGdJfigA6S7h1BXZOFb3eXsjy3iJV5RRyva8bHy4NRvW0zVo7tF0t0sAyUEs7lUHkdDy7MZt3ecsamxfD0lf2JkZlVT0uSvkmV1TTaBkrlFrE6v4RGi5VQf2/GGjNWjukTTaCv9PAJ52a1auau3c/sJXn4+3jy5BXnMHFAgqPDcmqS9E1k0/5yXly+m+YWK5sPHMeqITHM3zaRWXosQ3tG4C3lcMIF7SmpYcaCbLIPVXB5ZgKzfpkh6x2fgiR9E2i0tPDWmv0882UeACnRgVw+IIHxGbGkx4dIX6hwC5YWK699s4eXv8onLMCHZ389gAvSYhwdltORpO/GtNYszy3iqS92cqCsjj6xQfzP5Rmc11tmMRTuK+doJTPmZ7OrqJprhnbn0YnpBElXZRsp2XRTu4uqmfVZLmsKSkmNCeKdW4cxOjXa0WEJ0ekyEkJZdM9IXlqezxvf7mFNQSnPT84kKyXS0aE5PWnpu6CKuiZeWr6bd9cfJNDHkxnj+jA1K0mGrgtT2nygnAcWZHOgvI5bRvbkwYv74udt7gGE0tJ3E5YWKx9sOMgLy3dTVd/M9cOTuH9cHyLkYpYwscFJEXxx72hmL8njzTX7+HpXMS9OOZfM7mGODs0pSUvfRXxfUMoTn+Wyq6iaESmRPP7LdNLiQhwdlhBOZU1+KQ8uzKa4upG7zu/F3RemmnJ9ZbmQ68IOldfx1Oc7+TKnkG7h/jx6WT8uzoiTahwhTqGyvplZn+Xy0ZbDZCSE8OKUc+kbF+zosLqUJH0XVNto4R9fF/DP1fvwVIq7L+zNraN6mr6vUoiOWppTyB8/2U5VvYUZ4/vwm9EpeJpkDinp03chVqvm0+wjzF6SR1FVI78amMjMCWnEhcrQcyHOxMUZcQxJCuePn+xg9pI8VuQW8fzkTJKjAh0dmkNJS9+JbD1UwROf5fDDwQoyu4Xy2OUZDE4Kd3RYQrg0rTX/2XqExz7NwdKi+cNl/Zg6vIdbd5FKS9/JFVc18OzSXSzcfJioIF+eu2oAvx7UTaYzFsIOlFL8amA3slIieWjhNv70nx0syynk2asGEB9qvtXepKXvQK1TJ7yyMp/mFs0to3py1wW9CPaT1aiE6Axaa95bf5CnPt+Jl6fiiV9m8KuBiW7X6peWvpPRWrNiZzFPfp7LgbI6LuoXy6OX9TN9X6MQnU0pxdSsJEanRvHAgmxmLMhmWU4RT/3qHCKDzDG1uLT0u1h+UTWzFueyOr+U3jFBPDYxnTF9ZOoEIbpai1UzZ/VeXli2m2A/L/73yv5cnBHn6LDsQko2nUBlXTMvrdjNO+sOtE2dcH1WkkxzLISD7S6qZsaCrew4UsWVgxJ5/PIMQv1du4tVunccyNJi5YONh3hx2S4q65u5bngPZozrK1MnCOEk+sQG88mdI/nbygL+vqqAtXvKePaqAW47eaG09DvR93tKmfVZLnmF1WSlRPD45Rn0i5epE4RwVtmHKpixYCt7Smq5ISuJRy5NI8DH9drG0tLvYofK6/jfL3ayZIdt6oTXpg6SqROEcAGZ3cP4/HejeW7pLt76bh+r80t4YUomg5MiHB2a3UhL347qmiz8Y9Ue3li9F0+luOuCXtw2OkWmThDCBa3bW8bvP8zmaEU9vxmTwoxxffD1co2/ZWnpdzKtNZ9uPcrsJXkUVjVwxbkJPHxJP5k6QQgXlpUSyZf3jeGpz3N5/Zu9fJ1XwotXZ5KREOro0H4Waen/TNsOV/A/i3LYcrCCAd1CefzydLf6KiiEgFV5xcz8aBvltU3cOzaV357fy6kXLZKSzU5QXN3Ac1/u4kNj6oSZE/rK1AlCuLGKuiYe+zSHRdlHyewexguTM+kdE+TosE5Kkr4dNVpaePu7/fztq3yaWqzcMqond1/QW6ZOEMIkPt92jEf/s526phZmTkjjpvOSna6xJ336dnCyqRP+eFk/esrUCUKYymUD4hnaM5xHPtrOrMW5LMst5LmrMukeEeDo0DpEWvodcOLUCX+amM4vZOoEIUxNa82Hmw4za3EuAH+a2I8pQ7o7RWm2tPTP0olTJzx+eTpTZeoEIQS2ydumDO3Oeb0j+f2H2cz8aDtLc4qYfWV/YkKct3JPWvon0WLVfLDhIC8YUydcO6wHM8b1Mc0sfEKIM2O1auau3c/sJXn4+3jy50nncHlmgsPikZb+GVi7p4wnPsshr7Ca4T1tUyekJ8jUCUKIU/PwUNw8sidj+kQzY0E293zwA0tzCvnzpHMId7J5tiTpGw6V1/H0kp18sb2QxDB//nH9IC45R6ZOEEJ0XK/oID66YwSvfbOHl7/KZ/2+cp799QAuSItxdGhtTN+9U9dk4dWv9/D6t7apE+48vxe/GSNTJwghfp6co5U8sCCbvMJqrhnanUcnphPk2zXtbOneOQmtNYuyj/L0F7apEyadm8DDl6SZcs1MIYT9ZSSE8undI/nLinxe/2YPawpKee6qTEb0inRoXB0qQ1FKhSmlFiql8pRSO5VSI5RSEUqp5UqpfOPfcONYpZT6q1KqQCm1TSk1qN15phnH5yulpnXWkzqdbYcruOq1tdw7byvRwb4svGMEL18zUBK+EMKufL08mTkhjQ/vGIGXh+Laf65j1me5NDS3OCymDnXvKKXmAqu11nOUUj5AAPAHoFxrPVsp9TAQrrWeqZS6FLgHuBQYDrystR6ulIoANgFDAA1sBgZrrY+f6nHt3b3TOnXCwi2HiQz04aGL07hqsEydIITofHVNFp5ZksfctQfoFR3Ii1POJbN7WKc81s+ahkEpFQpsBVJ0u4OVUruA87XWx5RS8cDXWuu+SqnXje0P2h/X+qO1vt3Y/1/HnYy9kn6jpYV/fbefv60soNHSwi0je3L3hTJ1ghCi663JL+XBhdkUVzfy9+sGMuGceLs/xs/t0+8JlABvK6UysbXQ7wVitdbHjGMKgVhjOxE41O73Dxv7TrW/02it+cqYOmF/WR1j02J4dGK6TJ0ghHCYAd1DiQ/1o7i60SGrcnXkEb2AQcA9Wuv1SqmXgYfbH6C11kopu5QBKaWmA9MBevTocdbnKSiuZtbinXy7u4Re0YH86+ahnN/XecqmhBDmc7y2iRvf2kBeYRV/v24gYxwwnUtHkv5h4LDWer1xeyG2pF+klIpv171TbNx/BOje7ve7GfuOYOviab//6xMfTGv9BvAG2Lp3OvxM2gd8vI5LXl6Nn7cnj01M54YRMnWCEMKxSqobmTpnPfvLannjhiEOq90/bSbUWhcCh5RSfY1dY4FcYBHQWoEzDfjU2F4E3GhU8WQBlUY30FJgvFIq3Kj0GW/sszutoblF84dL+3HLqJ6S8IUQDnWssp6rX1/LwfI63r5pqEMHa3W0Q+ke4D2jcmcvcDO2D4wFSqlbgQPAFOPYL7BV7hQAdcaxaK3LlVJ/BjYax83SWpfb5VmcICbENkdOSXVjZ5xeCCE67FB5HdfNWcfx2mbeuXUYQ5Idu7Jeh5K+1nortlLLE409ybEauOsU53kLeOtMAjwbvl6eRAb6cKyyobMfSgghTmlvSQ3Xz1lPXVML7902vNNKNM+E247IjQv1o6hKkr4QwjF2FVZz/Zz1aK2ZNz2LfvHOMXGj23Z2x4f6SUtfCOEQO45Ucs0ba/H0gPm3j3CahA9unPRjQ/worKx3dBhCCJPZfOA41/5zHQE+Xiy4fYTTLZ7utkk/PtSP43XNDp3jQghhLmv3lHHDm+uJDPRhwR0jSIp0voGgbpv044zJ06RfXwjRFb7ZXcJNb28gMcyfBbePIDHMOSdwdN+kb6xRKf36QojOtiynkN/M3USv6CDmTc9y6jVy3bp6B6SlL4ToXJ9lH+X++Vs5JzGUuTcPIzTAuSdydPukLy19IURnWbj5MA8tzGZIcgRv3TS0y1bG+jnctnsnyNeLYF8vCiXpCyE6wTvrDvD7D7MZ2TuKuTcPc4mED27c0gdba1+SvhDC3uas3suTn+/kon4xvHLdIJdaU9vtk/4x6dMXQtjR377K54Xlu7msfzwvXX0uPl6u1WHiWtGeobgQP4qkpS+EsAOtNc8tzeOF5bu5cmAiL1/jegkf3Lylb1udpgFLixUvmV5ZCHGWtNbMWpzL29/t57rhPXhy0jkuu7a2W2fC2FA/rBpKamSKZSHE2bFaNX/4ZAdvf7efW0b25KkrXDfhg5sn/XijbFMu5gohzoalxcrvP8zmgw0HueuCXvxpYj+Uct2ED27evRMXYhsGLUlfCHGmmixW7pv/A19sL+T34/tw94Wpjg7JLtw76csALSHEWWhobuHu97ewYmcxj17Wj9tGpzg6JLtx66QfHuCNj5eHTMUghOiw+qYWpr+zidX5pTx5xTlMzUpydEh25dZJXykli6kIITqsptHCLW9vZNOBcp6fnMlVg7s5OiS7c+ukD8ZiKtLSF0KcRmVdMze+vYGcI5X89dqBTByQ4OiQOoVbV++ArYJHLuQKIX5KWU0j1/5zHTuPVvGP6we5bcIHE7T044yWvtba5UuthBD2V1zVwPVz1nOwvI5/ThvCL/pEOzqkTuX2Lf24UD+aLFaO1zU7OhQhhJM5UlHPlNfXcqSinrm3DHP7hA8mSPrxbWWbski6EOJHB8pqmfLaWspqm3j3tuFkpUQ6OqQu4fZJPzZERuUKIf5bQXENU15fS12ThQ9+k8WgHuGODqnLuH2ffryxQLpU8AghAHKPVnHDm+tRSjFv+gj6xgU7OqQu5fZJPzrYF08PJS19IQTbDldww5sbCPDx5L3bhpMSHeTokLqc2yd9Tw9FdJCvDNASwuQ27S/n5rc3Ehbozfu3ZdE9IsDRITmE2/fpg62CR6ZiEMK8vi8o5YY3NxAd7MuC20eYNuGDSZK+TMUghHmtyivmpn9tJCkygPm3j2i7zmdWpkj6sbJsohCm9OWOY0x/ZxN9YoP44DdZRAf7OjokhzNF0o8P9aO60UJ1gwzQEsIsPt16hLve/4H+iaG8d1sW4YE+jg7JKZgi6bfOqy/9+kKYw/yNB7lv/laGJofzzq3DCfX3dnRITsMcSb9tgJaslSuEu5v7/X5mfrSdManR/OvmYQT6un2R4hkxxf9G64UbmYpBCPf22jd7mL0kj/HpsfztuoH4enk6OiSnY4qkHxNiu3gjA7SEcE9aa/6yIp+Xv8rn8swEXpySibenKToyzpgpkr6ftycRgT4yFYMQbkhrzewv83j9m71MHtyN2b8egKeHTKN+Kh3+KFRKeSqlflBKLTZu91RKrVdKFSil5iulfIz9vsbtAuP+5HbneMTYv0spdbG9n8xPiQuRxVSEcDdWq+Z/FuXw+jd7uSEriWck4Z/WmXz/uRfY2e72M8BLWuvewHHgVmP/rcBxY/9LxnEopdKBa4AMYALwD6VUl3W4xckALSHcSotV88jH25m79gDTx6Qwa1IGHpLwT6tDSV8p1Q24DJhj3FbAhcBC45C5wBXG9iTjNsb9Y43jJwHztNaNWut9QAEwzB5PoiNkKgYh3Edzi5UZC7Yyf9Mhfjc2lUcuSZOV8Tqooy39vwAPAVbjdiRQobW2GLcPA4nGdiJwCMC4v9I4vm3/SX6njVJqulJqk1JqU0lJyRk8lZ8WH+JHWW0TjZYWu51TCNH1mixW7n5/C59uPcpDE/oyY1wfSfhn4LRJXyk1ESjWWm/ugnjQWr+htR6itR4SHW2/pctijQFaxVVSqy+Eq2pobmH6O5tYmlPE45enc+f5vR0dksvpSPXOSOCXSqlLAT8gBHgZCFNKeRmt+W7AEeP4I0B34LBSygsIBcra7W/V/nc63Y/LJjaYeoY9IVxVbaOF2+ZuYt2+Mp6+sj/XDuvh6JBc0mlb+lrrR7TW3bTWydguxK7UWl8PrAKuMg6bBnxqbC8ybmPcv1JrrY391xjVPT2BVGCD3Z7JabSOypUBWkK4nqqGZqa9tYEN+8t5cUqmJPyf4efU6c8E5imlngR+AN409r8JvKOUKgDKsX1QoLXOUUotAHIBC3CX1rrLOthl/h0hXFNFXRM3vrWB3KNVvHLtQC7pH+/okFzaGSV9rfXXwNfG9l5OUn2jtW4AJp/i958CnjrTIO0h2M+bIF8vKdsUwoWU1jQydc569pbW8saNg7kwLdbRIbk8U4zIbRUb4isDtIRwEYWVDVw3Zx3HKhp4a9pQRqVGOTokt2CqpB8f6i9TMQjhAg6V13H9nPWU1zYx95ZhDOsZ4eiQ3IapZiSKC5WpGIRwdvtKa7n69bVU1DXx7m3DJeHbmala+nEhfhRXN9Ji1TI/hxBOaHdRNdfPWU+LVTNv+gjSE0IcHZLbMV1Lv8WqKa2RAVpCOJsdRyq55o11KGDB7VmS8DuJqZJ++wFaQgjn8cPB41z3z3X4e3uy4PYR9I4JdnRIbstUST+2bdlESfpCOIv1e8uYOmc94YE+zL89i+SoQEeH5NZMlfRbW/qFMipXCKdQ3dDMTW9vpLaphV/0iaa0pokWq3Z0WG7NVBdyIwJ98PH04JiUbQrhFAJ8vLj9Fyksyyni32sP8O+1Bwjx8+K8XlGMSo1iVO8okiIDZBZNOzJV0ldKERvqS5F07wjhFDw9FPdd1If7LupDaU0j3+8pY01+CWvyS/kypxCAbuH+jOpt+xA4r1cUEbb6+TYAABGoSURBVIE+Do7atZkq6QPEh/jLhVwhnFBUkC+/zEzgl5kJaK3ZX1Zn+wAoKOXz7ceYt9G2HEdGQkjbt4ChyRH4eXfZAnxuwXRJPzbUj22HKxwdhhDiJyil6BkVSM+oQG4YkYylxcr2I5WsyS9lTUEpb63Zx+vf7MXHy4OhyeGM7B3F6N7RZCSEyJKJp2G6pB8f6seynAa01tJPKISL8PL0YGCPcAb2COeesanUNlrYsL+cNfmlfFdQyrNf7uJZdhEW4M3IXlG2D4HUKFk74yRMl/TjQvxotFipqGsmXPoGhXBJgb5eXNA3hgv6xgBQXN3A9wVlrCkoZU2+rTsIoEdEQFtX0Hm9IgkLkL958yX91rLNqgZJ+kK4iZhgP64YmMgVAxPRWrOnpJbvCkpZnV/Koq1HeX/9QZSC/omhRldQFIOSwk15PcC8Sb+ygX7xMsxbCHejlKJ3TBC9Y4KYdp7tekD24QrW5JexpqCEf367l1e/3oOftwdDkyMY1dvWHZQeb47rAaZL+jIVgxDm4uXpweCkCAYnRXDvRanUNFpYv9fWFfRdQSlPL8kDbON4zusVyehU24dAt3D3vB5guqQfHeSLh0Lm1RfCpIJ8vRjbL5ax/WyrcBVVNfCdcS1gTUEpi7fZrgf0jApkZO9IRvWOZkSvSEL9vR0Ztt2YLul7eXoQHewrUzEIIQDbnFxXDurGlYO6obUmv7im7QPg4y1HeHfdQTwU9O8WxmijK2hQUhi+Xq55PcB0SR8gLlQGaAkh/j+lFH1ig+kTG8wto3rSZLFdD1htlIa++s0eXllVgL+3J8N6RrR1BaXFBbtMCbg5k36IL/tKax0dhhDCydkGf0UwNDmCGeP6UNXQzPq95UZlUAlPfr4TgKggH0b2/nF8QHyov4MjPzVTJv34UH++31Pm6DCEEC4mxM+bcemxjEu3XQ84VlnfNkBsTUEZn249CkBKdGBbV1BWr0hC/JzneoApk35siB/VDRZqGy0E+pryv0AIYQfxof5MHtKdyUO6o7VmV1F12/WABZsOM3ftATw9FJndQo1J46I5t3sYPl6Om9XelBkvvt0ArV7RQQ6ORgjhDpRSpMWFkBYXwm2jU2iyWNly8HjbILFXVhXw15UFBPh4kpUS2dYVlBoT1KXXA0yZ9NsP0JKkL4ToDD5eHmSlRJKVEskD4/tSWd/M2j1lfGeMD1iZVwxAdLCv7VuAMX106wp/ncWcSV+WTRRCdLFQf28mnBPHhHPiADh8vI7vC8pYXVDKt7tL+OSHIwCkxgQxsncUN4xI6pRGqTmTfrvuHSGEcIRu4QFMGRrAlKHdsVo1eYXVfLO7hJdW7Cb/+/34eXvy8CVpdn9cU62R28rP25PwAG+OyQAtIYQT8PBQxIT48u3uEposVqZm9eD+camd8limbOmDrYKnsLLR0WEIIQSbDxznrve2cLyuiecnZ3LV4G6d9limTfrxoX4UVklLXwjhOFpr3ll3gD8vziUu1I+P7zyPjITQTn1M0yb9uFB/th+pdHQYQgiTqm9q4Q+fbOeTH45wYVoML005l9CAzh/EZd6kH+JHaU0TTRarQwdKCCHMZ39pLXe8u5ldRdXMGNeHuy/o3WVz+Zs26bcO0CqqapB1NIUQXWZFbhH3L9iKh1K8fdNQzjeWfOwqpk367cs2JekLITpbi1Xz0vLdvLKqgHMSQ3j1+sEOyT2S9GWAlhCik5XXNnHvvB9YnV/K1UO688SkDIetzytJX5K+EKITbTtcwW/f3UJJTSOzr+zPNcN6ODQe0yb9YF8vAnw8ZVSuEKJTaK2Zt/EQj3+aQ3SwLwvvGMGAbmGODuv0I3KVUt2VUquUUrlKqRyl1L3G/gil1HKlVL7xb7ixXyml/qqUKlBKbVNKDWp3rmnG8flKqWmd97ROTylFXKiftPSFEHbX0NzCzI+28cjH2xmeEsFn94xyioQPHWvpW4AHtNZblFLBwGal1HLgJuArrfVspdTDwMPATOASINX4GQ68CgxXSkUAjwNDAG2cZ5HW+ri9n1RHxYf6yVQMQgi7OlRexx3vbibnaBX3XNib+y7qg2cXlWN2xGlb+lrrY1rrLcZ2NbATSAQmAXONw+YCVxjbk4B/a5t1QJhSKh64GFiutS43Ev1yYIJdn80Zig3xo6hKpmIQQtjHql3FTPzbGg6W1zHnxiE8ML6vUyV8OMM+faVUMjAQWA/Eaq2PGXcVArHGdiJwqN2vHTb2nWr/iY8xHZgO0KNH517wiA/1o6iqgRardroXRgjhOqxWzd9WFvCXr3bTNzaY16YOJjkq0NFhnVSHh6IqpYKAj4D7tNZV7e/TWmtsXTY/m9b6Da31EK31kOjoaHuc8pTiQv2xWDVlNdLaF0Kcncq6Zm6du5GXVuzminMT+eTOkU6b8KGDLX2llDe2hP+e1vpjY3eRUipea33M6L4pNvYfAbq3+/Vuxr4jwPkn7P/67EP/+doWU6lqIKaTV6sRQrifHUcq+e17mymsbODPkzKYmpXUpUsfno2OVO8o4E1gp9b6xXZ3LQJaK3CmAZ+223+jUcWTBVQa3UBLgfFKqXCj0me8sc9hWqdiOCYVPEKIM7Rw82F+/er3NFs0828fwQ0jkp0+4UPHWvojgRuA7Uqprca+PwCzgQVKqVuBA8AU474vgEuBAqAOuBlAa12ulPozsNE4bpbWutwuz+IsyQAtIcSZarS08MRnuby//iAjUiL523UDiQrydXRYHXbapK+1XgOc6uNr7EmO18BdpzjXW8BbZxJgZ4oI8MHbU8kALSFEhxypqOfOdzeTfbiSO37Ri9+P74OXp2vN0mvaEblgW6LMtoKWJH0hnEmTxcrxuiZKaxopr22ivLaJRovVoTHVNVr468oCmixWXps6iAnnxDs0nrNl6qQPtou5kvSF6FyWFivH65opr22irKaR0tomymsaKattsv3UNFJWY0vupTWNVDVYHB3ySaXGBPHaDYPpFR3k6FDOmiT9UD9yjlad/kAhRBurVVNR30x5bSOlNU1GwrZtl9c2UdZ+u6aRivpm9EmKuj0URAT6EBHoQ2SgL/0SQogK9CEyyJeIQB+ignyICLRt+3k7vhslLsTP5bpzTmT6pB8f6seKnUVorV3iyrsQnUFrTVW9hbJao/VdY0vc7Vvf5e32H69rpsV68qE54QHetiQe5EtqTBBZKRFEBvoSGWRL7D8mcx/CAnxkYGQXM33Sjw3xo6HZSlW9pUvWpxSiK2itqWm0GAn7xxZ3+4Teel9ZTSPH65pobjl5Eg/x8yIyyJfIQB+SIgMYlBROZKCPLYkb+yONJB4R4OPyLWF3Z/qkHx/qD8CxqnpJ+sKp1TVZjIR9QleK0R9eZnSrlNc0UVprW//5ZAJ9PG3JOsiHxDA/BiSGEhHkQ2SgD1FGt0r7VrmsIe1eTJ/049oN0EqLC3FwNMJMGppb/qvLpK0rpd12+9Z5fXPLSc/j5+1BZKAvUUE+RAf5khYX8mNLPNCXiCAfoox/IwN9HLZik3AOkvRbF0iXCh7xM51YZtjW+q5p15VS++N9NY0nr1Dx8fRo6y6JDPKlV3RQ2/bJulUCfEz/ZyzOgOnfLTHBviglUzGI/89eZYZeHqqtQiUqyJceEQFt27aqlf9O4kG+XlJUIDqN6ZO+t6cH0UG+FMmoXLfXWWWG6QkhbYm7fZlhpNGtEuIvSVw4D9MnfbB18UhL3/U4oswwMsiXUH9vKTMULkuSPrYBFwfK6hwdhumdSZlhubF9JmWGUe36ydtf6AwP8JYyQ2EakvSxtfTX73PohJ9uy15lhkG+Xm2lhK1lhq0XO6XMUIiOk6SPLelX1jdT12SRSojTkDJDIVybZDh+XEylsLKBFBeeSOls2LvMMNK4iPlfZYZB/79CRT5chXAM+cvDNhUD2JZNdPWkb+8yw9ZELWWGQrgHSfr8OBWDM06xfGKZYVsyb1dm2L51/nPKDNu2pcxQCLclSZ8fF0jvirLNzioz7BMbRISUGQohTkOSPuDv40mov/dZDdCSMkMhhCuRpG+IbzdAq6vLDKOCfAkPkDJDIUTnk6RviAv14+tdxfT705dnVmbYWpkiZYZCCBcgSd8w7bzktkUgpMxQCOGuJIsZLugbwwV9YxwdhhBCdCrpRBZCCBORpC+EECYiSV8IIUxEkr4QQpiIJH0hhDARSfpCCGEikvSFEMJEJOkLIYSJKH2yeXidhFKqBDjQSaePAko76dz25ApxSoz2ITHah8QISVrr6JPd4dRJvzMppTZprYc4Oo7TcYU4JUb7kBjtQ2L8adK9I4QQJiJJXwghTMTMSf8NRwfQQa4Qp8RoHxKjfUiMP8G0ffpCCGFGZm7pCyGE6UjSF0IIE3GrpK+UekspVayU2tFuX4RSarlSKt/4N9zYr5RSf1VKFSiltimlBrX7nWnG8flKqWl2jrG7UmqVUipXKZWjlLrX2eJUSvkppTYopbKNGJ8w9vdUSq03YpmvlPIx9vsatwuM+5PbnesRY/8updTF9oqx3fk9lVI/KKUWO2OMSqn9SqntSqmtSqlNxj6nea2Nc4cppRYqpfKUUjuVUiOcKUalVF/j/6/1p0opdZ8zxWic+37j72WHUuoD4+/Iqd6PAGit3eYHGAMMAna02/cs8LCx/TDwjLF9KbAEUEAWsN7YHwHsNf4NN7bD7RhjPDDI2A4GdgPpzhSn8VhBxrY3sN547AXANcb+14DfGtt3Aq8Z29cA843tdCAb8AV6AnsATzu/5jOA94HFxm2nihHYD0SdsM9pXmvj/HOB24xtHyDM2WJsF6snUAgkOVOMQCKwD/Bv9z68ydnej1pr90r6xn9aMv+d9HcB8cZ2PLDL2H4duPbE44Brgdfb7f+v4zoh3k+Bcc4aJxAAbAGGYxtB6GXsHwEsNbaXAiOMbS/jOAU8AjzS7lxtx9kptm7AV8CFwGLjMZ0txv38/6TvNK81EIotWSlnjfGEuMYD3zlbjNiS/iFsHyhexvvxYmd7P2qt3at75xRitdbHjO1CINbYbn2RWh029p1qv90ZX+kGYmtJO1WcRrfJVqAYWI6txVGhtbac5PHaYjHurwQiOztG4C/AQ4DVuB3phDFqYJlSarNSarqxz5le655ACfC20U02RykV6GQxtncN8IGx7TQxaq2PAM8DB4Fj2N5fm3G+96Mpkn4bbfvodIoaVaVUEPARcJ/Wuqr9fc4Qp9a6RWt9LrbW9DAgzZHxnEgpNREo1lpvdnQspzFKaz0IuAS4Syk1pv2dTvBae2HrEn1Vaz0QqMXWVdLGCWIEwOgP/yXw4Yn3OTpG43rCJGwfoglAIDDBUfH8FDMk/SKlVDyA8W+xsf8I0L3dcd2MfafabzdKKW9sCf89rfXHzhongNa6AliF7atpmFLK6ySP1xaLcX8oUNbJMY4EfqmU2g/Mw9bF87KTxdjaAkRrXQx8gu0D1Jle68PAYa31euP2QmwfAs4UY6tLgC1a6yLjtjPFeBGwT2tdorVuBj7G9h51qvcjmCPpLwJar9JPw9aH3rr/RuNKfxZQaXxVXAqMV0qFG5/e4419dqGUUsCbwE6t9YvOGKdSKlopFWZs+2O75rATW/K/6hQxtsZ+FbDSaHktAq4xKhV6AqnABnvEqLV+RGvdTWudjO0r/0qt9fXOFKNSKlApFdy6je012oETvdZa60LgkFKqr7FrLJDrTDG2cy0/du20xuIsMR4EspRSAcbfeOv/o9O8H9vY+0KLI3+wvSGOAc3YWjC3Yusn+wrIB1YAEcaxCvg7tr7q7cCQdue5BSgwfm62c4yjsH0N3QZsNX4udaY4gQHAD0aMO4DHjP0p2N6ABdi+Yvsa+/2M2wXG/SntzvVHI/ZdwCWd9Lqfz4/VO04ToxFLtvGTA/zR2O80r7Vx7nOBTcbr/R9slS3OFmMgtpZwaLt9zhbjE0Ce8TfzDrYKHKd5P7b+yDQMQghhImbo3hFCCGGQpC+EECYiSV8IIUxEkr4QQpiIJH0hhDARSfpCCGEikvSFEMJE/g/clLJrSPF6XQAAAABJRU5ErkJggg==",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "# Hãy viết chương trình sử dụng GA giải quyết bài toán người bán hàng\n",
        "import random as rd\n",
        "import matplotlib.pyplot as mpl\n",
        "\n",
        "def MyPlot(n,cityPos,a):\n",
        "  mpl.cla()\n",
        "  X = [0]* (n+1)\n",
        "  Y = [0]* (n+1)\n",
        "  for i in range(n+1):\n",
        "    ii = a[i%n]\n",
        "    X[i] = cityPos[ii][0]\n",
        "    Y[i] = cityPos[ii][1]\n",
        "  mpl.plot(X,Y)\n",
        "\n",
        "citynum = 50\n",
        "cityPos = [(rd.randint(0,10000),rd.randint(0,10000)) for _ in range(citynum)]\n",
        "n = 1000\n",
        "ng = [None]*n\n",
        "f = [None]*n\n",
        "\n",
        "def KhoiTao():\n",
        "  global citynum,cityPos,n,ng;\n",
        "  for i in range(n):\n",
        "    a = list(range(citynum))\n",
        "    rd.shuffle(a)\n",
        "    ng[i] = a\n",
        "\n",
        "def Distance(a,b):\n",
        "  return ((a[0]-b[0])**2 + (a[1]-b[1])**2)**0.5\n",
        "\n",
        "def DanhGia():\n",
        "  global citynum,cityPos,n,ng,f;\n",
        "  for i in range(n):\n",
        "    distance = 0\n",
        "    for j in range(citynum):\n",
        "      distance += Distance(cityPos[ng[i][j]],cityPos[ng[i][(j+1)%citynum]])\n",
        "    f[i] = distance\n",
        "\n",
        "def PlotBest(num):\n",
        "  global citynum,cityPos,n,ng,f;\n",
        "  fc = [_ for _ in f]\n",
        "  fc.sort()\n",
        "  best = fc[0]\n",
        "  for i in range(n):\n",
        "    if f[i]==best:\n",
        "      if num%10==0:\n",
        "        MyPlot(citynum,cityPos,ng[i])\n",
        "        print(num,f[i])\n",
        "      break\n",
        "\n",
        "def LuaChon():\n",
        "  global citynum,cityPos,n,ng,f;\n",
        "  fc = [_ for _ in f]\n",
        "  fc.sort()\n",
        "  nguong = fc[80*n//100]\n",
        "  for i in range(n):\n",
        "    if f[i]>nguong:\n",
        "      ng[i] = [_ for _ in ng[rd.randrange(0,n)]]\n",
        "\n",
        "def LaiGhep():\n",
        "  global citynum,cityPos,n,ng,f;\n",
        "  for _ in range(30*n//100):\n",
        "    cha = rd.randrange(0,n)\n",
        "    me = rd.randrange(0,n)\n",
        "    # Gợi ý:\n",
        "    # Tìm 1 vị trí cắt \n",
        "    k = rd.randrange(0,citynum)\n",
        "    # Con thứ 1: Lấy đầu của cha và đuôi là những thành phố còn lại theo trật tự của mẹ\n",
        "    dau1 = ng[cha][0:k]\n",
        "    duoi1 = [0]*(citynum-k)\n",
        "    count = 0\n",
        "    #ngme = ng[me][k:]+ng[me][0:k]\n",
        "    for i in ng[me]:\n",
        "      if i not in dau1:\n",
        "        duoi1[count] = i\n",
        "        count +=1\n",
        "    # Con thứ 2: Lấy đầu của mẹ và đuôi là những thành phố còn lại theo trật tự của cha\n",
        "    dau2 = ng[me][0:k]\n",
        "    duoi2 = [0]*(citynum-k)\n",
        "    count = 0\n",
        "    #ngcha = ng[cha][k:]+ng[cha][0:k]\n",
        "    for i in ng[cha]:\n",
        "      if i not in dau2:\n",
        "        duoi2[count] = i\n",
        "        count +=1\n",
        "    ng[cha] = dau1+duoi1\n",
        "    ng[me] = dau2+duoi2\n",
        "\n",
        "\n",
        "def DotBien():\n",
        "  global citynum,cityPos,n,ng,f;\n",
        "  for _ in range(10*n//100):\n",
        "    dt = rd.randrange(0,n)\n",
        "    k1 = rd.randrange(0,citynum)\n",
        "    k2 = rd.randrange(0,citynum)\n",
        "    tmp = ng[dt][k1:k2+1]\n",
        "    tmp.reverse()\n",
        "    #ng[dt][k1:k2+1] = tmp\n",
        "    ng[dt][k1],ng[dt][k2] = ng[dt][k2],ng[dt][k1]\n",
        "\n",
        "\n",
        "KhoiTao()\n",
        "for _ in range(1000):\n",
        "  DanhGia()\n",
        "  PlotBest(_)\n",
        "  LuaChon()\n",
        "  LaiGhep()\n",
        "  DotBien()\n",
        "\n",
        "# a = list(range(citynum))\n",
        "# rd.shuffle(a)\n",
        "# MyPlot(citynum,cityPos,a)\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "SEovArXOj7bG",
        "outputId": "e61d63c9-544d-4b99-c35b-24ad4d095df4"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "([0, 1, 0, 1], [[0, 3], [3, 0]])\n"
          ]
        }
      ],
      "source": [
        "import random as rd\n",
        "D = [[0,3],[2,0],[0,4],[4,1]]\n",
        "k = 2\n",
        "\n",
        "\n",
        "def Distance(a,b):\n",
        "  sum = 0\n",
        "  for i in range(len(a)):\n",
        "    sum +=(a[i]-b[i])**2\n",
        "  return sum\n",
        "\n",
        "def argmin(x,mu):\n",
        "  id = -1\n",
        "  dis = 0\n",
        "  for i in range(len(mu)):\n",
        "    d = Distance(x,mu[i])\n",
        "    if id ==-1 or dis>d:\n",
        "      id = i\n",
        "      dis = d\n",
        "  return id\n",
        "\n",
        "def kmean(D,k):\n",
        "  # B1: chọn ngẫu nhiên k phần tử từ D để làm tâm của k nhóm\n",
        "  mu = [list(x) for x in rd.sample(D,k)]\n",
        "  C = []\n",
        "  count = 0\n",
        "  while True:\n",
        "    # B2: gán phần tử của D vào nhóm có khoảng cách tới trọng tâm gần nhất\n",
        "    C_old = C[:]\n",
        "    C = [argmin(x,mu) for x in D]\n",
        "    if C_old==C:\n",
        "      break\n",
        "    # B3: tính lại tâm của k nhóm\n",
        "    for i in range(len(mu)):\n",
        "      for j in range(len(mu[i])):\n",
        "        mu[i][j] = 0\n",
        "    sl = [0]*len(mu)\n",
        "    for i in range(len(D)):\n",
        "      for j in range(len(D[i])):\n",
        "        mu[C[i]][j] += D[i][j]\n",
        "      sl[C[i]] += 1\n",
        "    for i in range(len(mu)):\n",
        "      if sl[i]!=0:\n",
        "        mu[i] = [mu[i][j]//sl[i] for j in range(len(mu[i]))]\n",
        "      else:\n",
        "        mu[i] = rd.sample(D,1)[0][:]\n",
        "  return C,mu\n",
        "\n",
        "print(kmean(D,k))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "BYyYCOkHymQO",
        "outputId": "1fb47cc0-8214-4332-c342-f1b09e636571"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "start\n",
            "stop\n"
          ]
        }
      ],
      "source": [
        "from PIL import Image\n",
        "import requests\n",
        "import numpy as np\n",
        "\n",
        "#url = \"https://i1-vnexpress.vnecdn.net/2022/04/27/b771c25b143ad5648c2b9-1651032829.jpg?w=220&h=132&q=100&dpr=1&fit=crop&s=-UBBbtkkHypEgeUz5Z2U2w\"\n",
        "#url = \"https://1.bp.blogspot.com/-D4NvUDjIa84/YJQS5gnwbpI/AAAAAAAAoHQ/aCNJB38Z-Z0Qu2tY1GE4onQaiWMjMQ2VQCLcBGAsYHQ/s2048/bungalows-3840x2160-4k-hd-wallpaper-reef-french-polynesia-water-594.webp\"\n",
        "url = \"https://www.luavietours.com/contents_luavietours/upload/Image/10-dia-danh-dep-me-hon-tren-the-gioi-hinh-10.jpg\"\n",
        "im = Image.open(requests.get(url, stream=True).raw)\n",
        "\n",
        "pix_val = list(im.getdata())\n",
        "\n",
        "print(\"start\")\n",
        "C,mu = kmean(rd.sample(pix_val,1000),15)\n",
        "print(\"stop\")\n",
        "new_pix_val = [None]*len(pix_val)\n",
        "for i in range(len(pix_val)):\n",
        "  new_pix_val[i] = tuple(mu[argmin(pix_val[i],mu)])\n",
        "\n",
        "\n",
        "array = np.array(new_pix_val, dtype=np.uint8)\n",
        "array = array.reshape((im.size[1],im.size[0],3))\n",
        "\n",
        "# Use PIL to create an image from the new array of pixels\n",
        "new_image = Image.fromarray(array)\n",
        "new_image.save('new.png')\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {
        "id": "pHzIlmcCskxt"
      },
      "outputs": [],
      "source": [
        "def f(x):\n",
        "  #black box\n",
        "  return (4-x)**4"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "C15qAI9hrhjW",
        "outputId": "1f473b28-7c7b-43d3-9fb7-3cfc898e0180"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "84934656 100\n",
            "0.5 84934656 100\n",
            "0.25 84934656 100\n",
            "0.125 84934656 100\n",
            "0.0625 84934656 100\n",
            "0.03125 84934656 100\n",
            "0.015625 84934656 100\n",
            "0.0078125 84934656 100\n",
            "0.00390625 84934656 100\n",
            "0.001953125 84934656 100\n",
            "0.0009765625 84934656 100\n",
            "0.00048828125 84934656 100\n",
            "0.000244140625 84934656 100\n",
            "0.0001220703125 84934656 100\n",
            "6.103515625e-05 84934656 100\n",
            "3.0517578125e-05 84934656 100\n",
            "6.103515625e-05 20728.106632713807 -7.9988578567281365\n",
            "0.0001220703125 17963.859754987 -7.577103447553668\n",
            "0.000244140625 13703.166769368618 -6.819451284323463\n",
            "0.00048828125 8432.071585550379 -5.582604659204549\n",
            "0.0009765625 3824.45599913677 -3.863980305263226\n",
            "0.001953125 1265.404056976084 -1.9642701383105534\n",
            "0.00390625 344.0279522720653 -0.30673780470067435\n",
            "0.0078125 87.51574428649992 0.9414080042290605\n",
            "0.015625 21.947077519661228 1.8355668622959338\n",
            "0.03125 5.489719332403732 2.469308976638018\n",
            "0.0625 1.3725564356464648 2.9176130371787674\n",
            "0.125 0.343144569080666 3.2346337940468923\n",
            "0.25 0.08578637585352152 3.4588039972804014\n",
            "0.5 0.021446603789869147 3.617316592691066\n",
            "1.0 0.005361651437988085 3.729401961455236\n",
            "2.0 0.0013404128795677535 3.8086582912529527\n",
            "4.0 0.00033510321806522414 3.864700980405527\n",
            "8.0 8.377580382260282e-05 3.9043291459549065\n",
            "16.0 2.094395099088614e-05 3.932350490314353\n",
            "32.0 5.235987737524978e-06 3.9521645729806227\n",
            "64.0 1.3089969406355426e-06 3.966175245133241\n",
            "128.0 3.272492349052826e-07 3.976082286466376\n",
            "256.0 8.181230872838896e-08 3.98308762256979\n",
            "512.0 2.0453077183074898e-08 3.9880411432329694\n",
            "1024.0 5.113269296053316e-09 3.9915438112846764\n",
            "2048.0 1.2783173234048208e-09 3.994020571617113\n",
            "4096.0 3.1957933081327954e-10 3.995771905642967\n",
            "8192.0 7.98948327361328e-11 3.9970102858083383\n",
            "16384.0 1.9973708184078904e-11 3.997885952821265\n",
            "32768.0 4.9934270460973065e-12 3.9985051429041625\n",
            "65536.0 1.2483567615374488e-12 3.9989429764106257\n",
            "131072.0 3.120891903925783e-13 3.9992525714520744\n",
            "262144.0 7.802229759215699e-14 3.9994714882053195\n",
            "524288.0 1.950557439814542e-14 3.999626285726044\n",
            "1048576.0 4.876393599640931e-15 3.999735744102658\n",
            "2097152.0 1.2190983999072675e-15 3.999813142863021\n",
            "4194304.0 3.0477459997346073e-16 3.9998678720513294\n",
            "8388608.0 7.619364999347989e-17 3.9999065714315107\n",
            "16777216.0 1.9048412497573022e-17 3.9999339360256654\n",
            "33554432.0 4.762103124139784e-18 3.9999532857157565\n",
            "67108864.0 1.1905257809062455e-18 3.999966968012834\n",
            "134217728.0 2.9763144516819462e-19 3.99997664285788\n",
            "268435456.0 7.440786125862329e-20 3.9999834840064197\n",
            "536870912.0 1.8601965300376703e-20 3.9999883214289436\n",
            "1073741824.0 4.650491317159868e-21 3.999991742003215\n",
            "2147483648.0 1.1626228254378395e-21 3.999994160714479\n",
            "4294967296.0 2.9065570444646987e-22 3.9999958710016177\n",
            "8589934592.0 7.266392513093886e-23 3.999997080357254\n",
            "17179869184.0 1.8165980808898906e-23 3.9999979355008293\n",
            "34359738368.0 4.541494958715283e-24 3.999998540178656\n",
            "68719476736.0 1.1353736188510107e-24 3.999998967750456\n",
            "137438953472.0 2.8384334442761986e-25 3.9999992700893863\n",
            "274877906944.0 7.096080587402273e-26 3.9999994838753103\n",
            "549755813888.0 1.7740186403718423e-26 3.9999996350448095\n",
            "1099511627776.0 4.435039041098617e-27 3.99999974193782\n",
            "2199023255552.0 1.10875599449397e-27 3.9999998175226374\n",
            "4398046511104.0 2.771871104832779e-28 3.9999998709692393\n",
            "8796093022208.0 6.929583506021305e-29 3.9999999087617844\n",
            "17592186044416.0 1.732348726089172e-29 3.999999935485278\n",
            "35184372088832.0 4.330636140200989e-30 3.999999954381823\n",
            "70368744177664.0 1.0825412110655593e-30 3.9999999677439555\n",
            "140737488355328.0 2.7057638452547734e-31 3.9999999771927737\n",
            "281474976710656.0 6.761464235758132e-32 3.9999999838746114\n",
            "562949953421312.0 1.688894399820335e-32 3.999999988600111\n",
            "1125899906842624.0 4.214885159581794e-33 3.999999991942572\n",
            "2251799813685248.0 1.0500538110920254e-33 3.999999994307502\n",
            "4503599627370496.0 2.606876369439322e-34 3.9999999959818133\n",
            "9007199254740992.0 6.426687793598538e-35 3.999999997168629\n",
            "1.8014398509481984e+16 1.5621995996258584e-35 3.9999999980119187\n",
            "3.602879701896397e+16 3.690771727904161e-36 3.9999999986139487\n",
            "7.205759403792794e+16 8.226437806237395e-37 3.999999999047636\n",
            "1.4411518807585587e+17 1.6235270751289402e-37 3.999999999365232\n",
            "2.8823037615171174e+17 2.455358362332419e-38 3.9999999996041518\n",
            "5.764607523034235e+17 1.95369282081649e-39 3.9999999997897606\n",
            "1.152921504606847e+18 2.090374921085616e-41 3.999999999932383\n",
            "2.305843009213694e+18 1.9163331503483257e-44 4.000000000011766\n",
            "1.152921504606847e+18 1.9163331503483257e-44 4.000000000011766\n",
            "2.305843009213694e+18 1.0651350143513936e-47 3.9999999999981934\n",
            "1.152921504606847e+18 1.0651350143513936e-47 3.9999999999981934\n",
            "2.305843009213694e+18 5.821600823019821e-51 4.000000000000276\n",
            "1.152921504606847e+18 5.821600823019821e-51 4.000000000000276\n",
            "2.305843009213694e+18 3.1679280235396166e-54 3.999999999999958\n",
            "1.152921504606847e+18 3.1679280235396166e-54 3.999999999999958\n",
            "2.305843009213694e+18 2.5489470578119236e-57 4.000000000000007\n",
            "1.152921504606847e+18 2.5489470578119236e-57 4.000000000000007\n"
          ]
        }
      ],
      "source": [
        "def f1(x):\n",
        "  delta = 0.000000001\n",
        "  return (f(x+delta/2)-f(x-delta/2))/delta\n",
        "\n",
        "def main():\n",
        "  alpha = 1\n",
        "  x = 100\n",
        "  print(f(x),x)\n",
        "  for i in range(100):\n",
        "    x_new = x - alpha*f1(x)\n",
        "    if f(x_new)>f(x):\n",
        "      alpha /=2\n",
        "    else:\n",
        "      x = x_new\n",
        "      alpha *=2\n",
        "    print(alpha, f(x),x)\n",
        "\n",
        "main()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "id": "Qf0f-dBZxhIY"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0.5 10525 [0, 0, 0, 0]\n",
            "1.9073486328125e-06 106.06878404036378 [0.000693850459983973, 0.05711389685929452, 0.13340143625802142, 0.07613013451981719]\n",
            "7.62939453125e-06 91.71342547916637 [0.00041085763624821095, 0.08313791765966617, 0.11665252850840477, 0.10750839415164014]\n",
            "1.9073486328125e-06 83.99863888347403 [0.0002069035009294451, 0.10232961909351204, 0.10694213650136541, 0.13042720201372485]\n",
            "1.9073486328125e-06 79.5868725290897 [2.801446371972563e-05, 0.1167917338019345, 0.09837041415857785, 0.14732625471450372]\n",
            "1.9073486328125e-06 77.20198949462659 [-0.00012177255739680669, 0.12795073257558395, 0.09225497563964828, 0.16007880241259692]\n",
            "1.9073486328125e-06 75.82842955788092 [-0.00025035755656912986, 0.13622349392227573, 0.08746413742696586, 0.16922641952571366]\n",
            "7.62939453125e-06 75.0772523527515 [-0.0003670287229739014, 0.1426648640236692, 0.08364279771950414, 0.17605568493806323]\n",
            "1.9073486328125e-06 74.67211480741193 [-0.00046356103743463474, 0.14750136857285692, 0.08142000251974374, 0.18096825730090926]\n",
            "1.9073486328125e-06 74.4405667746853 [-0.0005551038471794017, 0.15124692434943826, 0.07946636087693147, 0.18450951783594322]\n",
            "1.9073486328125e-06 74.31419856721952 [-0.0006407997773464486, 0.15422619915363942, 0.07807338379251623, 0.18710585725398501]\n",
            "1.9073486328125e-06 74.24096178299975 [-0.0007209635700104093, 0.15652414270891774, 0.07698555413622203, 0.18889172653565414]\n",
            "7.62939453125e-06 74.20001824245806 [-0.0007999357932699175, 0.158399963023155, 0.07612060031896059, 0.1901480293867588]\n",
            "1.9073486328125e-06 74.17676540360306 [-0.000872172900611215, 0.159877443518672, 0.07561823889939674, 0.1909869498342975]\n",
            "1.9073486328125e-06 74.1627240818244 [-0.0009440573964171646, 0.1610982006190914, 0.07517928459375911, 0.19151743087184267]\n",
            "1.9073486328125e-06 74.15405929344566 [-0.0010154084098882004, 0.16213605445055335, 0.07486820284326325, 0.19183660531221403]\n",
            "1.9073486328125e-06 74.1482797960421 [-0.0010848127197753132, 0.16300095398306425, 0.07462712205896986, 0.19198316396712603]\n",
            "1.9073486328125e-06 74.1442089736226 [-0.0011543623792205533, 0.16376148757020248, 0.07446022348562012, 0.19201648806935218]\n",
            "1.9073486328125e-06 74.14117428683466 [-0.0012233398447649172, 0.16442904073004705, 0.07434301484116172, 0.19196351802759323]\n",
            "1.9073486328125e-06 74.13851982497013 [-0.0012910730698889508, 0.1650113002367834, 0.07424163574732391, 0.19184438882347088]\n",
            "1.9073486328125e-06 74.13632993945241 [-0.0013585126983054374, 0.1655383541565727, 0.07416938643925364, 0.19168398129314596]\n",
            "1.9073486328125e-06 74.13425069489841 [-0.001430558840446539, 0.16605661651858356, 0.07412480917948551, 0.19148342911315328]\n",
            "1.9073486328125e-06 74.13234026329197 [-0.0015034703540922926, 0.166538693107213, 0.0740909516610487, 0.19125650269014757]\n",
            "1.9073486328125e-06 74.13052700890343 [-0.001579190333264157, 0.16700422170428883, 0.07407146936257561, 0.19100732286258248]\n",
            "1.9073486328125e-06 74.12887249610826 [-0.00165296896234156, 0.16742672373059672, 0.0740546147069189, 0.1907553150759644]\n",
            "1.9073486328125e-06 74.12730345966808 [-0.0017286711445461825, 0.16783498145782946, 0.0740447549876536, 0.1904945654572279]\n",
            "7.62939453125e-06 74.12580481126105 [-0.0018068147984771996, 0.16823288227039132, 0.07403883660208034, 0.19022640393032736]\n",
            "1.9073486328125e-06 74.12440729475358 [-0.0018849627579512265, 0.1686109229994292, 0.07404013472669002, 0.1899631544268203]\n",
            "7.62939453125e-06 74.12311629420664 [-0.0019631708617044046, 0.16896989828395723, 0.0740406113228899, 0.18970447305342145]\n",
            "7.62939453125e-06 74.12189885550451 [-0.002043779288904803, 0.16932530704293544, 0.07405499931707143, 0.18944848419252516]\n",
            "1.9073486328125e-06 74.12080095232346 [-0.002119213624244133, 0.16963864307337828, 0.07405095500561723, 0.18921092314339422]\n",
            "7.62939453125e-06 74.11973327172548 [-0.002200453761683121, 0.16996473709824853, 0.07406148934054503, 0.18896737505432107]\n",
            "1.9073486328125e-06 74.11880490036421 [-0.0022759759806941448, 0.1702525375428521, 0.07406121874798517, 0.18874582595952988]\n",
            "1.9073486328125e-06 74.11788575130477 [-0.002356874435266237, 0.17054946551640335, 0.07406746441413035, 0.1885186995257561]\n",
            "7.62939453125e-06 74.1170155381898 [-0.0024415184047012184, 0.17084564930711418, 0.07406964335810906, 0.18828896806651635]\n",
            "7.62939453125e-06 74.11616199950916 [-0.002528091150676403, 0.17113837603175577, 0.0740855268502638, 0.18806745310651865]\n",
            "1.9073486328125e-06 74.11544128377672 [-0.002614249861899331, 0.17141651508770844, 0.07409953225760518, 0.18785580667751267]\n",
            "1.9073486328125e-06 74.11470093091212 [-0.002698642033343218, 0.17167253602805455, 0.0740930980909251, 0.18765141047875497]\n",
            "1.9073486328125e-06 74.11403519484897 [-0.0027865564940991977, 0.17193061162681342, 0.0740994258541639, 0.18745110779154378]\n",
            "3.0517578125e-05 74.11346518325699 [-0.00287475587376185, 0.17218100762011196, 0.07411802659099538, 0.18726242603462948]\n",
            "2.9802322387695312e-08 74.11309416944992 [-0.0029244256246437135, 0.17231279441422573, 0.07410945854431858, 0.18715434699119274]\n",
            "7.62939453125e-06 74.11297072373112 [-0.002944775597702243, 0.1723664826895234, 0.07410888148340168, 0.1871116833199827]\n",
            "6.938893903907228e-18 74.11288860649239 [-0.002957054562358522, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "6.938893903907228e-18 74.11288860649239 [-0.0029570545623586087, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "6.938893903907228e-18 74.11288860649239 [-0.0029570545623586954, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "6.938893903907228e-18 74.11288860649239 [-0.002957054562358782, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "6.938893903907228e-18 74.11288860649239 [-0.002957054562358869, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "1.734723475976807e-18 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n",
            "4.336808689942018e-19 74.11288860649239 [-0.0029570545623589517, 0.17239936263021508, 0.07411173428012512, 0.18708707081183393]\n"
          ]
        }
      ],
      "source": [
        "data = [[22,28,146,34],\n",
        "[36,46,169,57],\n",
        "[24,39,160,48],\n",
        "[22,25,156,38],\n",
        "[27,34,161,47],\n",
        "[29,29,168,50],\n",
        "[26,38,154,54],\n",
        "[23,23,153,40],\n",
        "[31,42,160,62],\n",
        "[24,27,152,39],\n",
        "[23,35,155,46],\n",
        "[27,39,154,54],\n",
        "[31,38,157,57],\n",
        "[25,32,162,53],\n",
        "[23,25,142,32]]\n",
        "\n",
        "def y(x,a):\n",
        "  return a[0] + a[1]*x[1]+a[2]*x[2]+a[3]*x[3]\n",
        "\n",
        "\n",
        "def e(a):\n",
        "  sum = 0\n",
        "  for x in data:\n",
        "    sum += (x[0] - y(x,a))**2\n",
        "  return sum\n",
        "\n",
        "def e1(a,i):\n",
        "  d = 0.00001\n",
        "  aa = a[:]\n",
        "  aa[i] += d\n",
        "  return (e(aa) - e(a))/d\n",
        "\n",
        "# Tìm a sao cho e(a) nhỏ nhất\n",
        "def main():\n",
        "  a = [0,0,0,0]\n",
        "  alpha = 1\n",
        "  for _ in range(10000):\n",
        "    aa = a[:]\n",
        "    for i in range(4):\n",
        "      aa[i] = a[i] - alpha*e1(a,i)\n",
        "    if e(aa)>e(a):\n",
        "      alpha /=2\n",
        "    else:\n",
        "      a = aa\n",
        "      alpha *= 2\n",
        "    if _%100==0:\n",
        "      print(alpha,e(a),a)\n",
        "\n",
        "main()\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "wnL6wOggu4aX"
      },
      "outputs": [],
      "source": [
        "# train độc lập\n",
        "from sklearn import datasets\n",
        "import math\n",
        "iris = datasets.load_iris()\n",
        "X = iris.data\n",
        "Y = iris.target\n",
        "\n",
        "def o(W,x):\n",
        "  sum = W[0]\n",
        "  for i in range(len(W)-1):\n",
        "    sum += W[i+1]*x[i]\n",
        "  return math.exp(sum)/(1+math.exp(sum))\n",
        "\n",
        "def e(W,X,y):\n",
        "  sum = 0;\n",
        "  for i in range(len(X)):\n",
        "    sum += (y[i]-o(W,X[i]))**2\n",
        "  return sum\n",
        "def e1(W,i,X,y):\n",
        "  d = 0.00001\n",
        "  WW = W[:]\n",
        "  WW[i] += d\n",
        "  return (e(WW,X,y) - e(W,X,y))/d\n",
        "\n",
        "def learnModel(X,y):\n",
        "  W = [0]*(len(X[0])+1)\n",
        "  alpha = 1\n",
        "  for _ in range(100):\n",
        "    W_new = W[:]\n",
        "    for i in range(len(W)):\n",
        "      W_new[i] = W[i] - alpha*e1(W,i,X,y)\n",
        "    e_new = e(W_new,X,y)\n",
        "    e_ = e(W,X,y)\n",
        "    if e_new>e_:\n",
        "      alpha /=2\n",
        "    elif e_new<e_:\n",
        "      W = W_new\n",
        "      alpha *= 2\n",
        "    else:\n",
        "      break\n",
        "  return W\n",
        "\n",
        "model = [None]*3\n",
        "for i in range(3):\n",
        "  y = list(Y)[:]\n",
        "  for j in range(len(y)):\n",
        "    if y[j]==i:\n",
        "      y[j] = 1\n",
        "    else:\n",
        "      y[j] = 0\n",
        "  model[i] = learnModel(X,y)\n",
        "\n",
        "#softMax\n",
        "for i in range(len(X)):\n",
        "  maxj = 0\n",
        "  maxV = 0\n",
        "  for j in range(3):\n",
        "    o_ = o(model[j],X[i])\n",
        "    if maxV<o_:\n",
        "      maxV=o_\n",
        "      maxj=j\n",
        "  print(Y[i],maxj)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "XJIEmsrbsyKz"
      },
      "outputs": [],
      "source": [
        "# train có liên kết softMax\n",
        "from sklearn import datasets\n",
        "import math\n",
        "iris = datasets.load_iris()\n",
        "X = iris.data\n",
        "Y = iris.target\n",
        "\n",
        "def o(W,x):\n",
        "  sum = W[0]\n",
        "  for i in range(len(W)-1):\n",
        "    sum += W[i+1]*x[i]\n",
        "  return math.exp(sum)/(1+math.exp(sum))\n",
        "\n",
        "def o_fM(W_all,x):\n",
        "  return [o(W_all[j],x) for j in range(len(W_all))]\n",
        "\n",
        "def e(W_all,X,Y):\n",
        "  sum = 0\n",
        "  for i in range(len(X)):\n",
        "    O = [0]*len(W_all)\n",
        "    O[Y[i]] = 1\n",
        "    o = o_fM(W_all,X[i])\n",
        "    for j in range(len(W_all)):\n",
        "      sum += (O[j]-o[j])**2\n",
        "  return sum\n",
        "\n",
        "def e1(W_all,j,i,X,Y):\n",
        "  d = 0.00001\n",
        "  WW = [W[:] for W in W_all]\n",
        "  WW[j][i] += d\n",
        "  return (e(WW,X,Y) - e(W_all,X,Y))/d\n",
        "\n",
        "def learnModel(X,Y):\n",
        "  W_all = [[0]*(len(X[0])+1) for _ in range(3)]\n",
        "  alpha = 1\n",
        "  for _ in range(100):\n",
        "    W_new = [W[:] for W in W_all]\n",
        "    for j in range(len(W_all)):\n",
        "      for i in range(len(W_all[j])):\n",
        "        W_new[j][i] = W_all[j][i] - alpha*e1(W_all,j,i,X,Y)\n",
        "    e_new = e(W_new,X,Y)\n",
        "    e_ = e(W_all,X,Y)\n",
        "    if e_new>e_:\n",
        "      alpha /=2\n",
        "    elif e_new<e_:\n",
        "      W_all = W_new\n",
        "      alpha *= 2\n",
        "    else:\n",
        "      break\n",
        "  return W_all\n",
        "\n",
        "model = learnModel(X,Y)\n",
        "print(model)\n",
        "for i in range(len(X)):\n",
        "  maxj = 0\n",
        "  maxV = 0\n",
        "  oo = o_fM(model,X[i])\n",
        "  for j in range(3):\n",
        "    if maxV<oo[j]:\n",
        "      maxV=oo[j]\n",
        "      maxj=j\n",
        "  print(maxj,Y[i])\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2T6Xku67_vEf",
        "outputId": "f2d41a64-446f-4578-f914-c60347601338"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0.3333333333333333\n",
            "0.3333333333333333\n",
            "0.3333333333333333\n",
            "0.3333333333333333\n",
            "0.3333333333333333\n",
            "0.3333333333333333\n",
            "0.3333333333333333\n",
            "0.3333333333333333\n",
            "0.3333333333333333\n",
            "0.3333333333333333\n",
            "0.3333333333333333\n",
            "0.3333333333333333\n",
            "0.3333333333333333\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.4\n",
            "0.4\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.6666666666666666\n",
            "0.7133333333333334\n",
            "0.7133333333333334\n",
            "0.6733333333333333\n",
            "0.6733333333333333\n",
            "0.6933333333333334\n",
            "0.6933333333333334\n",
            "0.6933333333333334\n",
            "0.8066666666666666\n",
            "0.8066666666666666\n",
            "0.8066666666666666\n",
            "0.7\n",
            "0.8733333333333333\n",
            "0.8733333333333333\n",
            "0.8733333333333333\n",
            "0.7\n",
            "0.7\n",
            "0.8066666666666666\n",
            "0.7733333333333333\n",
            "0.7733333333333333\n",
            "0.9133333333333333\n",
            "0.9133333333333333\n",
            "0.9133333333333333\n",
            "0.8266666666666667\n",
            "0.9266666666666666\n",
            "0.9266666666666666\n",
            "0.7733333333333333\n",
            "0.7733333333333333\n",
            "0.7733333333333333\n",
            "0.92\n",
            "0.8666666666666667\n",
            "0.8666666666666667\n",
            "0.9666666666666667\n",
            "0.9666666666666667\n",
            "0.9666666666666667\n",
            "0.86\n",
            "0.86\n",
            "0.9666666666666667\n",
            "0.8666666666666667\n",
            "0.8666666666666667\n",
            "0.8666666666666667\n",
            "0.96\n",
            "0.96\n",
            "0.8933333333333333\n",
            "0.8933333333333333\n",
            "0.9666666666666667\n",
            "0.8733333333333333\n",
            "0.8733333333333333\n",
            "0.8733333333333333\n",
            "0.96\n",
            "0.96\n",
            "0.8866666666666667\n",
            "0.8866666666666667\n",
            "0.96\n",
            "0.96\n",
            "0.8866666666666667\n",
            "0.8866666666666667\n",
            "0.9666666666666667\n",
            "0.9666666666666667\n",
            "0.9666666666666667\n",
            "0.9533333333333334\n",
            "0.9666666666666667\n",
            "0.9\n",
            "0.9\n",
            "0.9\n",
            "0.9666666666666667\n",
            "0.9666666666666667\n"
          ]
        }
      ],
      "source": [
        "# Bài tập: \n",
        "# Hãy thêm 1 lớp ẩn với số lượng nơron tại lớp đó tùy ý. \n",
        "# Xây dựng chương trình tìm tham số W tại tất cả các nơron đó.\n",
        "\n",
        "# train có liên kết softMax\n",
        "from sklearn import datasets\n",
        "import math\n",
        "import random as rd\n",
        "iris = datasets.load_iris()\n",
        "X = iris.data\n",
        "Y = iris.target\n",
        "\n",
        "def o(W,x):\n",
        "  sum = W[0]\n",
        "  for i in range(len(W)-1):\n",
        "    sum += W[i+1]*x[i]\n",
        "  return math.exp(sum)/(1+math.exp(sum))\n",
        "\n",
        "def layout(WW,x):\n",
        "  return [o(W,x) for W in WW]\n",
        "\n",
        "def network(WWW,x):\n",
        "  for WW in WWW:\n",
        "    x = layout(WW,x)\n",
        "  return x\n",
        "\n",
        "def e(WWW,X,Y):\n",
        "  sum = 0\n",
        "  for i in range(len(X)):\n",
        "    net_o = network(WWW,X[i])\n",
        "    O = [0]*len(net_o)\n",
        "    O[Y[i]] = 1\n",
        "    for j in range(len(net_o)):\n",
        "      sum += (O[j]-net_o[j])**2\n",
        "  return sum\n",
        "\n",
        "def e1(WWW,k,j,i,X,Y):\n",
        "  d = 0.0000001\n",
        "  WWW_ = [[W[:] for W in WW] for WW in WWW]\n",
        "  WWW_[k][j][i] += d\n",
        "  return (e(WWW_,X,Y) - e(WWW,X,Y))/d\n",
        "\n",
        "def acc(model):\n",
        "  count = 0\n",
        "  for i in range(len(X)):\n",
        "    maxj = 0\n",
        "    maxV = 0\n",
        "    oo = network(model,X[i])\n",
        "    for j in range(len(oo)):\n",
        "      if maxV<oo[j]:\n",
        "        maxV=oo[j]\n",
        "        maxj=j\n",
        "    if Y[i] == maxj:\n",
        "      count +=1\n",
        "  print(count/len(X))\n",
        "\n",
        "def learnModel(X,Y,struct,droprate):\n",
        "  WWW = [[[0]*(struct[i]+1)]*struct[i+1] for i in range(len(struct)-1)]\n",
        "  alpha = 1\n",
        "  for _ in range(100):\n",
        "    W_new = [[W[:] for W in WW] for WW in WWW]\n",
        "    for k in range(len(WWW)):\n",
        "      for j in range(len(WWW[k])):\n",
        "        for i in range(len(WWW[k][j])):\n",
        "          if (rd.random()>droprate):\n",
        "            W_new[k][j][i] = WWW[k][j][i] - alpha*e1(WWW,k,j,i,X,Y)\n",
        "    e_new = e(W_new,X,Y)\n",
        "    e_ = e(WWW,X,Y)\n",
        "    if e_new>e_:\n",
        "      alpha /=2\n",
        "    elif e_new<e_:\n",
        "      WWW = W_new\n",
        "      alpha *= 2\n",
        "    acc(WWW)\n",
        "  return WWW\n",
        "\n",
        "model = learnModel(X,Y,[4,10,3],0)\n"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "tf",
      "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.9.6"
    },
    "vscode": {
      "interpreter": {
        "hash": "52ee2977380704a66854748a73250e0671a9318bd5b3fd45a3df9f851ae61629"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}