Ders3 - Döngülerle problem çözme.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Asal sayıları listelemek\n",
    "==============\n",
    "Verilen bir $N$ sayısından küçükeşit bütün asalları listeleyen bir program yazalım.\n",
    "\n",
    "Bir önceki yazıda, belli bir sayının asal olup olmadığını tespit eden bir program yazmıştık. Burada, o programı 2 ile $N$ arasındaki her tamsayı için çalıştıracağız."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bir pozitif tamsayı girin: 20\n",
      "2\n",
      "3\n",
      "5\n",
      "7\n",
      "11\n",
      "13\n",
      "17\n",
      "19\n"
     ]
    }
   ],
   "source": [
    "N = int(input(\"Bir pozitif tamsayı girin: \"))\n",
    "x = 2\n",
    "while x <= N:\n",
    "    i = 2\n",
    "    while i*i <= x:\n",
    "        if x % i == 0:\n",
    "            break\n",
    "        i += 1\n",
    "    else:\n",
    "        print(x)\n",
    "    x += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Gördüğünüz gibi, verilen bir sayının asallığını tespit etmek için kullandığımız döngünün etrafına bir döngü daha sararak $N$'ye kadar olan bütün sayıları yokluyoruz."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Alıştırma.** Yukarıdaki programı değiştirerek ilk $k$ asal sayıyı basmasını sağlayın. Yani, meselâ 6 girildiğinde 2, 3, 5, 7, 11, 13 sayılarını çıkarsın.\n",
    "\n",
    "Verilen bir sayının asal çarpanlarını listelemek\n",
    "=================\n",
    "\n",
    "Bu öncekine göre biraz daha zahmetli bir iş, ama ilkokulda öğrendiğimiz yöntemi uyarlamak yeterli.\n",
    "\n",
    "Verilen sayıya $N$ diyelim. Bir $x$ değişkenine başta 2 atayalım. Eğer $x$ asal sayıysa, ve $N$ sayısı $x$'e bölünüyorsa, $x$'i ekrana basalım. Ardından $N$'yi $x$'e bölebildiğimiz kadar bölelim, böylece içinde $x$ çarpanı kalmasın. $N$ birden büyük olduğu sürece, $x$'i bir artırıp tekrarlayalım."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bir pozitif tamsayı girin: 13860\n",
      "2 3 5 7 11 "
     ]
    }
   ],
   "source": [
    "N = int(input(\"Bir pozitif tamsayı girin: \"))\n",
    "x = 2\n",
    "while N > 1:\n",
    "    # x asal mı?\n",
    "    asal = True\n",
    "    i = 2\n",
    "    while i*i <= x:\n",
    "        if x % i == 0:\n",
    "            asal = False\n",
    "            break\n",
    "        i += 1\n",
    "\n",
    "    if asal and N % x == 0:\n",
    "        print(x, end=\" \")\n",
    "        while N % x == 0 :\n",
    "            N = N / x\n",
    "    x += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bu programdaki döngüde `else` kullanmadık.\n",
    "\n",
    "Fibonacci dizisi\n",
    "========\n",
    "\n",
    "Temel programlama derslerinin olmazsa olmazı Fibonacci dizisi şöyle tanımlanır:\n",
    "\n",
    "$$\\begin{array}{rcl} F_0 &=& 1 \\\\ F_1 &=& 1 \\\\ F_n &=& F_{n-1} + F_{n-2}\\end{array}$$\n",
    "\n",
    "Yani, dizideki her terim, önceki iki terimin toplamıdır. Dizideki sayılar şöyle gider: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...\n",
    "\n",
    "Fibonacci dizisinin ilk elli terimini ekrana yazacak bir program yazalım."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "2\n",
      "3\n",
      "5\n",
      "8\n",
      "13\n",
      "21\n",
      "34\n",
      "55\n",
      "89\n",
      "144\n",
      "233\n",
      "377\n",
      "610\n",
      "987\n",
      "1597\n",
      "2584\n",
      "4181\n",
      "6765\n",
      "10946\n",
      "17711\n",
      "28657\n",
      "46368\n",
      "75025\n",
      "121393\n",
      "196418\n",
      "317811\n",
      "514229\n",
      "832040\n",
      "1346269\n",
      "2178309\n",
      "3524578\n",
      "5702887\n",
      "9227465\n",
      "14930352\n",
      "24157817\n",
      "39088169\n",
      "63245986\n",
      "102334155\n",
      "165580141\n",
      "267914296\n",
      "433494437\n",
      "701408733\n",
      "1134903170\n",
      "1836311903\n",
      "2971215073\n",
      "4807526976\n",
      "7778742049\n",
      "12586269025\n",
      "20365011074\n"
     ]
    }
   ],
   "source": [
    "a, b = 1, 1\n",
    "print(a)\n",
    "print(b)\n",
    "i = 2\n",
    "while i<=50:\n",
    "    a,b = b, a+b\n",
    "    print(b)\n",
    "    i += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Döngüde, Python'a özgü bir çokuz ataması yaptığımıza dikkat edin:\n",
    "\n",
    "    a,b = b, a+b\n",
    "Bu işlemin sonunda `b`'nin eski değeri `a`'ya, `a+b` toplamının eski değeri de `b`'ye atanır. Başka dillerde çokuz ataması bulunmayabilir. Aynı işi başka türlü nasıl yaparız? İlk akla gelen şey şu olabilir:\n",
    "\n",
    "    a = b\n",
    "    b = a + b   # yanlış\n",
    "Bu yanlış, çünkü ikinci atamada eşitliğin sağ tarafında `a`'nın yeni değeri kullanılıyor. Bir önceki ifadede `a`'ya `b`'nin değerini atamıştık. Böylece atamanın sonunda sadece `b`'yi iki katına çıkarmış oluruz.\n",
    "\n",
    "Doğru yöntem, eski değerler için ayrı değişkenler kullanmaktır. Yukarıdaki programı bu yaklaşımla tekrar yazalım:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 1\n",
    "b = 1\n",
    "print(a)\n",
    "print(b)\n",
    "i = 2\n",
    "while i<=50:\n",
    "    a_eski = a\n",
    "    b_eski = b\n",
    "    a = b_eski\n",
    "    b = a_eski + b_eski\n",
    "    print(b)\n",
    "    i += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "İki programı karşılaştırınca, çoklu atama kullanan programın daha sade ve okunaklı olduğunu görebiliyoruz.\n",
    "\n",
    "Collatz dizisi\n",
    "=========\n",
    "Collatz dizisi pozitif tamsayılardan oluşur. Diziyi oluşturma kuralı şöyledir:\n",
    "\n",
    "$n_i$ çift sayıysa: $n_{i+1} = n_i/2$\n",
    "\n",
    "$n_i$ tek sayıysa: $n_{i+1} = 3n_i+1$\n",
    "\n",
    "Dizi 1'e ulaştığında durur. Sözgelişi, diziye 13 ile başlarsak\n",
    "\n",
    "13, 40,20, 10, 5, 16, 8, 4, 2,1\n",
    "\n",
    "elde ederiz. <a href=\"http://en.wikipedia.org/wiki/Collatz_conjecture\">Collatz dizisi</a> adı verilen bu diziyi basit bir Python programıyla üretebiliriz:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Başlangıç değeri: 11\n",
      "34 17 52 26 13 40 20 10 5 16 8 4 2 1 "
     ]
    }
   ],
   "source": [
    "n = int(input(\"Başlangıç değeri: \"))\n",
    "while n > 1:\n",
    "    if n % 2 == 0:  # n çift sayıysa\n",
    "        n = n/2\n",
    "    else:   # n tek sayıysa\n",
    "        n = 3*n + 1\n",
    "    print(int(n), end=\" \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Seriler\n",
    "=====\n",
    "Terimleri belli bir formüle göre değişen serileri hesaplamak için döngüleri kullanabiliriz. Sözgelişi, $\\pi$ sayısını Leibniz formülü ile hesaplayalım.\n",
    "\n",
    "$$\\frac{\\pi}{4} = \\sum_{i=0}^{\\infty} (-1)^i \\frac{1}{2i+1} = 1 - \\frac{1}{3} + \\frac{1}{5} - \\frac{1}{7} + \\ldots$$\n",
    "\n",
    "Bu eşitlik sonsuz sayıda terim kullandığımızda tam doğru olur. Pratikte bu mümkün olmadığından toplamayı bir yerde bitirmek gerekir, bu da _kesme hatası_ (truncation error) denen hataya yol açacaktır. Buna ek olarak, bilgisayarın içinde sayıları tam olarak temsil edememekten kaynaklanan _yuvarlama hatası_ (roundoff error) da vardır.\n",
    "\n",
    "Bu toplamı nerede kesmeliyiz? Önce, serinin yavaş yakınsadığına dikkat edin. Her yeni terim, büyüklük olarak bir öncekine yakın. O yüzden çok sayıda toplama yapmak gerekecek ($\\pi$ sayısını hesaplamak için daha iyi formüller vardır. Bazılarını alıştırmalarda kullanacağız). Diyelim $\\pi$'yi virgülden sonra dört basamak doğrulukta belirlemek istiyoruz. O zaman hata payının $10^{-5}$ kadar olmasını isteriz. Terimlerin mutlak değeri tekdüze olarak azaldığından, mutlak değeri $10^{-5}$'den küçük terimlere geldiğimizde döngüyü durdururuz.\n",
    "\n",
    "Başka bir deyişle, döngüyü durdurmak için $1/(2i+1) \\leq 10^{-5}$, veya, $2i+1 \\geq 10^5$ şartı geçerlidir. Böylece yaklaşık 50 000 terim toplamak gerektiğini görürüz."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pi ~ 3.1415726535897814\n",
      "50001 terim toplandı.\n"
     ]
    }
   ],
   "source": [
    "toplam = 0.0 # ara toplam\n",
    "isaret = 1 # +1 veya -1 olarak dönüşümlü olarak değişecek\n",
    "payda = 1.0  # 1,3,5,7,...\n",
    "terim = isaret / payda\n",
    "sayac = 1\n",
    "while abs(terim) > 0.00001:\n",
    "    toplam += terim\n",
    "    payda += 2\n",
    "    isaret *= -1\n",
    "    terim = isaret / payda\n",
    "    sayac += 1\n",
    "\n",
    "print(\"pi ~\", 4*toplam)\n",
    "print(sayac,\"terim toplandı.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fonksiyon tablolama\n",
    "==========\n",
    "Aşağıdaki program, $x$ değişkenini 0 ile 1 arasında 0.1 adımlarla artırarak, $x$ ve $\\sin(x)$ değerlerini bir tablo olarak yazar.\n",
    "\n",
    "Bu programda _matematik modülünü_ kullanıyoruz. Matematiksel fonksiyon ve sabitlerin bulunduğu `math` modülü Python standart kütüphanesine dahildir. Bu modülden daha sonra bahsedeceğiz. Ayrıntılı bilgi için Python <a href=\"http://docs.python.org/2/library/math.html\">başvuru belgelerine</a> bakabilirsiniz."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x sin x\n",
      "0.0 0.0\n",
      "0.1 0.09983341664682815\n",
      "0.2 0.19866933079506122\n",
      "0.30000000000000004 0.2955202066613396\n",
      "0.4 0.3894183423086505\n",
      "0.5 0.479425538604203\n",
      "0.6 0.5646424733950354\n",
      "0.7 0.644217687237691\n",
      "0.7999999999999999 0.7173560908995227\n",
      "0.8999999999999999 0.7833269096274833\n",
      "0.9999999999999999 0.8414709848078964\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "x = 0.0\n",
    "dx = 0.1\n",
    "print(\"x\", \"sin x\")\n",
    "while x <= 1.0:\n",
    "    print(x, math.sin(x))\n",
    "    x += dx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bu çıktı pek göze hitap etmiyor, hizalanma iyi değil. Daha iyi bir görünüm için _dize biçimlendirme_ (string formatting) uygulayabiliriz."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x      sin x \n",
      "0.0000 0.0000\n",
      "0.1000 0.0998\n",
      "0.2000 0.1987\n",
      "0.3000 0.2955\n",
      "0.4000 0.3894\n",
      "0.5000 0.4794\n",
      "0.6000 0.5646\n",
      "0.7000 0.6442\n",
      "0.8000 0.7174\n",
      "0.9000 0.7833\n",
      "1.0000 0.8415\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "x = 0.0\n",
    "dx = 0.1\n",
    "print(\"{:6s} {:6s}\".format(\"x\", \"sin x\"))\n",
    "while x <= 1.0:\n",
    "    print(\"{:1.4f} {:1.4f}\".format(x, math.sin(x)))\n",
    "    x += dx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dize biçimlendirme, belli kurallara göre hazırlanmış bir kalıp dizesine işlem yapar. Bu kalıp içinde `{` ve `}` işaretleri bir _yer tutucu_ görevi görür. Bu örnekte `{:6s}` yer tutucusu 6 karakterlik yer içine bir dize (\"s\") geleceğini belirtiyoruz. Daha sonraki `{:1.4f}` yer tutucusu ise bir reel sayının (\"f\") ondalık noktadan önce bir basamak, noktadan sonra ise dört basamak olarak gösterileceğini düzenliyor.\n",
    "\n",
    "Dize biçimlendirme kalıplarını oluşturma kuralları çok zengindir. Buradaki amaçlarımız için daha fazla derine girmemiz gerekmiyor. Meraklısı için daha ayrıntılı bilgi [şurada bulunabilir](https://pyformat.info/).\n",
    "\n",
    "_____________\n",
    "\n",
    "Başka bir örnek olarak, sinüs fonksiyonunun değişik derecelerdeki Taylor yaklaştırımını veren bir tablo üretelim. Bilindiği gibi, $\\sin$ fonksiyonunun 0 çevresindeki Taylor açılımı şu şekildedir:\n",
    "\n",
    "$$\\sin x = x - \\frac{x^3}{6} + \\frac{x^5}{120} - \\frac{x^7}{5040} + \\ldots$$\n",
    "\n",
    "Artan derecelerdeki yaklaştırım fonksiyonlarını şöyle tanımlayabiliriz:\n",
    "\n",
    "$$\\begin{eqnarray}\n",
    "f_1(x) &=& x - \\frac{x^3}{6} \\\\\n",
    "f_2(x) &=& x - \\frac{x^3}{6} + \\frac{x^5}{120}\\\\\n",
    "f_3(x) &=& x - \\frac{x^3}{6} + \\frac{x^5}{120} - \\frac{x^7}{5040}\n",
    "\\end{eqnarray}$$\n",
    "\n",
    "ve 0 ile 1 arasında değişen $x$ değerleri için, her satıra $x$, $f_1(x)$, $f_2(x)$, $f_3(x)$, $\\sin x$ değerlerini ekrana yazalım."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x      f1     f2     f3     sin x \n",
      "0.0000 0.0000 0.0000 0.0000 0.0000\n",
      "0.1000 0.0998 0.0998 0.0998 0.0998\n",
      "0.2000 0.1987 0.1987 0.1987 0.1987\n",
      "0.3000 0.2955 0.2955 0.2955 0.2955\n",
      "0.4000 0.3893 0.3894 0.3894 0.3894\n",
      "0.5000 0.4792 0.4794 0.4794 0.4794\n",
      "0.6000 0.5640 0.5646 0.5647 0.5646\n",
      "0.7000 0.6428 0.6442 0.6443 0.6442\n",
      "0.8000 0.7147 0.7174 0.7174 0.7174\n",
      "0.9000 0.7785 0.7834 0.7835 0.7833\n",
      "1.0000 0.8333 0.8417 0.8419 0.8415\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "x = 0.0\n",
    "dx = 0.1\n",
    "print(\"{:6s} {:6s} {:6s} {:6s} {:6s}\".format(\"x\", \"f1\", \"f2\", \"f3\", \"sin x\"))\n",
    "while x <= 1.0:\n",
    "    f1 = x - x**3 /6\n",
    "    f2 = f1 + x**5/120\n",
    "    f3 = f2 + x**7/5040\n",
    "    print(\"{:1.4f} {:1.4f} {:1.4f} {:1.4f} {:1.4f}\".format(x, f1, f2, f3, math.sin(x)))\n",
    "    x += dx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "İteratif denklem sistemleri\n",
    "============\n",
    "Diyelim, radyoaktif bir $A$ izotopu bozunuyor ve yine radyoaktif olan $B$ izotopunu üretiyor, o da bozunarak kararlı (radyoaktif olmayan) $C$ izotopunu üretiyor. $A$'nın bozunma sabiti (birim zamanda bozunan atomların oranı) $\\lambda_A$, $B$'ninki ise $\\lambda_B$ olsun. Düzenli zaman aralıklarında $A$, $B,$ ve $C$ atomlarının sayılarını veren bir program yazalım.\n",
    "\n",
    "Denklemler şöyle olur:\n",
    "\n",
    "$$\\begin{eqnarray}\n",
    "a_{t+1} &=& a_t - a_t \\lambda_A \\Delta t\\\\\n",
    "b_{t+1} &=& b_t - b_t \\lambda_B \\Delta t + a_t \\lambda_A \\Delta t\n",
    "\\end{eqnarray}$$\n",
    "\n",
    "Burada $a_t$ ve $b_t$, $t$ adımında $A$ ve $B$ atomlarının sayısı, $\\Delta t$ ise zaman adımı. Birinci denklemde her adımda bir miktar $A$ atomu kaybediliyor. İkinci denklemde ise her adımda bir miktar $B$ atomu kaybediliyor, buna karşılık kaybedilen $A$ atomu kadar yeni $B$ atomu ekleniyor. Toplam atom sayısı $N$ sabit olduğundan $C $ \n",
    "atomları için ayrı bir denklem yazmaya lüzum yok, $c_t =N-a_t-b_t$ ile bulunabilir.\n",
    "\n",
    "Somut bir örnek olarak, $^{135} \\mathrm{I} \\rightarrow ^{135}\\mathrm{Xe} \\rightarrow ^{135} \\mathrm{Cs}$ <a href=\"https://en.wikipedia.org/wiki/Decay_chain#Beta_decay_chains_in_uranium_.26_plutonium_fission_products\">zincirini ele alalım</a>. İyot-135'in yarılanma ömrü 6.57 saat, Ksenon-135'in ise 9.14 saattir. Sezyum-135 kararlı izotop olmasa da, yarılanma ömrü 2.3 milyon yıl olduğundan, diğerlerine göre sabit sayılır. Yarılanma ömrü $\\tau$ ise, bozunma sabiti $\\lambda = \\ln 2 / \\tau$ <a href=\"https://en.wikipedia.org/wiki/Radioactive_decay#Radioactive_decay_rates\">olur</a>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  saat      I     Xe     Cs\n",
      "     0   1000      0      0\n",
      "     1    894     94     11\n",
      "     2    800    171     28\n",
      "     3    715    234     50\n",
      "     4    640    283     75\n",
      "     5    572    322    104\n",
      "     6    512    352    135\n",
      "     7    458    373    167\n",
      "     8    409    388    201\n",
      "     9    366    398    235\n",
      "    10    327    402    269\n",
      "    11    293    402    303\n",
      "    12    262    400    337\n",
      "    13    234    394    370\n",
      "    14    209    386    403\n",
      "    15    187    377    435\n",
      "    16    167    366    465\n",
      "    17    150    354    495\n",
      "    18    134    341    523\n",
      "    19    120    328    551\n",
      "    20    107    314    577\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "a,b,c = 1000, 0, 0\n",
    "N = a+b+c\n",
    "\n",
    "lam_a = math.log(2) / 6.57 # I-135, 1/saat biriminde\n",
    "lam_b = math.log(2) / 9.14 # Xe-135, 1/saat biriminde\n",
    "t = 0\n",
    "\n",
    "# Sütun başlıkları sağa yaslansın.\n",
    "print(\"{:>6s} {:>6s} {:>6s} {:>6s}\".format(\"saat\", \"I\",\"Xe\",\"Cs\"))\n",
    "\n",
    "# Bir saatlik aralıklarla a,b,c miktarını ekrana bas.\n",
    "while t <= 20:\n",
    "    print(\"{:6d} {:6d} {:6d} {:6d}\".format(t, int(a), int(b), int(c)))\n",
    "    a = (1-lam_a)*a\n",
    "    b = (1-lam_b)*b + lam_a*a\n",
    "    c = N-a-b\n",
    "    t += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Görüyoruz ki $^{135} \\mathrm{I}$ miktarı sürekli azalıyor ve $ ^{135} \\mathrm{Cs}$ sürekli artıyor. Geçiş izotopu $^{135}\\mathrm{Xe}$ ise önce artıyor, onuncu saatte zirveye ulaşıyor, ve sonra sürekli azalıyor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}