Problemleri daha basit alt problemlere bölerek çözme yöntemi. Problemleri daha basit alt problemlere bölerek çözme yöntemi



Yüklə 0,96 Mb.
tarix07.11.2018
ölçüsü0,96 Mb.
#78156



Problemleri daha basit alt problemlere bölerek çözme yöntemi.

  • Problemleri daha basit alt problemlere bölerek çözme yöntemi.

  • Alt problemler de kendi içlerinde başka alt problemlere bölünebilir.

  • Alt problemler çözülebilecek kadar küçülünce bölme işlemi durur.

  • Özyinelemeli bir algoritma bir problemi çözmek için problemi iki veya daha fazla alt probleme bölen bir yöntemdir.



Ozyinelemeli Tanim

  • Ozyinelemeli Tanim

    • basamak(n) = 1 -> if (–9 <= n <= 9)
    • 1 + basamak(n/10) -> degilse
  • Ornek

    • basamak(321) =
    • 1 + basamak(321/10) = 1 +basamak(32) =
    • 1 + [1 + basamak(32/10)] = 1 + [1 + basamak(3)] =
    • 1 + [1 + (1)] =
    • 3


int basamakSayisi(int n) {

  • int basamakSayisi(int n) {

  • if ((-10 < n) && (n < 10))

  • return 1

  • else

  • return 1 + basamakSayisi (n/10);

  • }



f(x) problemini çözmek istiyorsak fakat direkt olarak çözemiyorsak

  • f(x) problemini çözmek istiyorsak fakat direkt olarak çözemiyorsak

  • Varsayalım y`nin x`den küçük herhangi bir değeri için f(y)’yi çözebiliyoruz

  • f(x)`i çözmek için f(y)`yi kullanırız

  • Bu yöntemin çalışabilmesi için f(x)`in direkt olarak hesaplanabildiği en az bir x değerinin olması gerekir. (e.g. taban durumu)



static int power(int k, int n) {

  • static int power(int k, int n) {

  • // k`nın n. üssü

  • if (n == 0)

  • return 1;

  • else

  • return k * power(k, n – 1);

  • }



public int sum(int num) {

  • public int sum(int num) {

  • int result;

  • if (num == 1) {

  • result = 1;

  • } else {

  • result = num + sum(num - 1);

  • }

  • return result;

  • }



5! = 5*4*3*2*1 4! = 4*3*2*1 3! = 3*2*1 2! = 2*1 1! = 1

  • 5! = 5*4*3*2*1 4! = 4*3*2*1 3! = 3*2*1 2! = 2*1 1! = 1



public int faktoriyel(int N) {

  • public int faktoriyel(int N) {

  • if (N == 0) return 1;

  • return N*faktoriyel(N-1);

  • }





public double faktoriyelGoster(int n, int sayac) {

  • public double faktoriyelGoster(int n, int sayac) {

  • double fakt;

  • if (n <= 0) {

  • System.out.println("Taban Duruma ulasti");

  • fakt = 1;

  • } else {

  • sayac++;

  • System.out.println(sayac + ". program cagiriyor ");

  • fakt = n * faktoriyelGoster(n - 1, sayac);

  • //System.out.println("Faktoriyel = " + fakt);

  • }

  • System.out.println(sayac + ". programdan Cikiyor ");

  • sayac--;

  • return fakt;

  • }



  • 1. program cagiriyor

  • 2. program cagiriyor

  • 3. program cagiriyor

  • 4. program cagiriyor

  • 5. program cagiriyor

  • Taban Duruma ulasti

  • 5. programdan Cikiyor

  • 5. programdan Cikiyor

  • 4. programdan Cikiyor

  • 3. programdan Cikiyor

  • 2. programdan Cikiyor

  • 1. programdan Cikiyor





  • public int fibonacci(int sayi) {

  • if ( ( sayi == 0 ) || ( sayi == 1 )

  • return sayi;

  • else

  • return fibonacci( sayi - 1 ) + fibonacci( sayi - 2 );

  • }





Legend has it that in a temple in the Far East, priests are attempting to move a stack of golden disks from one diamond peg to another.

  • Legend has it that in a temple in the Far East, priests are attempting to move a stack of golden disks from one diamond peg to another.

  • The initial stack has 64 disks threaded onto one peg and arranged from bottom to top by decreasing size.

  • The priests are attempting to move the stack from one peg to another under the constraints that exactly one disk is moved at a time and at no time may a larger disk be placed above a smaller disk.

  • Three pegs are provided, one being used for temporarily holding disks.

  • Supposedly, the world will end when the priests complete their task, so there is little incentive for us to facilitate their efforts.





Move n - 1 disks from peg 1 to peg 2, using peg 3 as a temporary holding area.

  • Move n - 1 disks from peg 1 to peg 2, using peg 3 as a temporary holding area.

  • Move the last disk (the largest) from peg 1 to peg 3.

  • Move the n - 1 disks from peg 2 to peg 3, using peg 1 as a temporary holding area.



//Towers of Hanoi

  • //Towers of Hanoi

  • // recusively move disks through towers

  • public void solveTowers( int disks, int sourcePeg, int destinationPeg,

  • int tempPeg ) {

  • // base case -- only one disk to move

  • if ( disks == 1 ) {

  • System.out.println(sourcePeg + " -> " +destinationPeg );

  • return;

  • } // end if

  • // recursion step -- move disk to tempPeg, then to destinationPeg

  • // move ( disks - 1 ) disks from sourcePeg to tempPeg recursively

  • solveTowers( disks - 1, sourcePeg, tempPeg, destinationPeg );

  • // move last disk from sourcePeg to destinationPeg

  • System.out.println(sourcePeg + " -> " +destinationPeg );

  • // move ( disks - 1 ) disks from tempPeg to destinationPeg

  • solveTowers( disks - 1, tempPeg, destinationPeg, sourcePeg );

  • } // end method solveTowers



1 --> 3

  • 1 --> 3

  • 1 --> 2

  • 3 --> 2

  • 1 --> 3

  • 2 --> 1

  • 2 --> 3

  • 1 --> 3



Yüklə 0,96 Mb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə