BBS#514 YAPISAL#PROGRAMLAMA …burcucan/BBS514... · 2017-10-04 · BBS65146TYapısal6Programlama6(Structured6Programming) 39 AreaTCircumference6Problem(cont.) Solve… 5. Report

BBS 514

YAPISAL PROGRAMLAMA(STRUCTURED PROGRAMMING)

LECTURE 1: ALGORITHMS

BBS 514 -‐ Yapısal Programlama (Structured Programming)

1

Lecturer: Burcu Can

İçerik

¨ Bilgisayar için problem çözme süreci ve Pólya’nın Nasıl Çözmeli listesi¨ Algoritma kavramı¨ Yalancı kod¨ Kontrol yapıları

Problem Çözme

¨ Problem çözme (sözlük anlamı): çözülmesi gereken mesele, sorun veya aşılması gereken engel için çözüm bulma.

Problem Çözme

¨ Nasıl Çözmeli: Matematiksel Yöntem için Yeni Bir Bakış -George Pólya

¨ Matematiksel problemler için yazılmış¨ Liste oldukça genel ve bilgisayar için de uyarlanabilir.

Bilgisayarla ilişkili problemleri çözmek için de kullanabiliriz.

Problem Çözme

¨ Problemleri nasıl çözersiniz?¨ Problemi anla

¤ Bir plan oluşturn Planı gerçekleştir.

n Gözden geçir.

¨ Eğer bu yöntemle çözülmezse, Pólya şunu tavsiye ediyor:¤ “Bir problemi çözemiyorsanız, çözmenin mümkün olduğu daha basit bir problem vardır.”

¤ “Eğer problemi çözemiyorsanız, onunla ilişkili başka bir problemi çözmeyeçalışın.”

Stratejiler

¨ Sorular sor!¤ Problem hakkında ne biliyorum?

¤Çözümü bulmak için elimde nasıl bilgiler mevcut?

¤Nasıl bir çözüm bulunması gerekiyor?

¤Özel durumlar var mı?

Stratejiler

¨ Sorular sor! Tekerleği yeniden icat etme!¤ Benzer problemler farklı biçimlerde karşımıza çıkabilir.¤ İyi bir programcı, daha önce çözülmüş bir görevi tanıyarak başka birproblemin çözümü için onu yeni çözüme dahil eder.

¤ Birbirine benzer iki problem tanımlayın!

Stratejiler

¨ Böl ve Yönet¤ Büyük bir problemi daha küçük parçalarına böl ve alt problemleriçöz.

¤Her alt görev başa çıkılır oluncaya dek ‘böl ve yönet’ taktiği tekrartekrar uygulanabilir.

Bilgisayarda Problem Çözme

• Analiz ve tanımlama aşamasıAnaliz etTanımla

• Algoritma geliştirme aşamasıAlgoritma geliştirmeAlgoritmayı test et

• Uygulama aşamasıAlgoritmayı kodlaAlgoritmayı test et

• Bakım aşamasıKullanHataları/eksiklikleri gider

Tekrar eden kısımlarhangileridir?

Kod Geliştirme Aşamaları

Algoritmalar

¨ Algoritma¤ Bir problemi veya alt problemibelli bir zamanda, sonlusayıda veriyle çözmek içingerekli olan komutlar kümesi

Algoritma

¨ Yemek tarifleri, yol tarifleri en bilinen algoritmalardandır.¨ Kek tarifi:

¤ Fırını 180 dereceye getirelim.¤ Yumurtaları ve toz şekeri bir kabın içersine döküp köpük köpük olana kadarmikserle çırpalım. Burada dikkat etmeniz gereken şey, 3 yumurtayı aynı andadeğil, tek tek kırıp köpük yapıp üzerine diğer yumurtayı kırıp işleme devam edin.

¤ Köpük köpük yaptıktan sonra diğer tüm malzemeleri sırasıyla kabın içerisinedökün ve çırpmaya devam edin.

¤ Kolay kekin harcını yaptıktan sonra istediğiniz şekildeki kalıba dökün ve fırınaverin.

¤ Yaklaşık olarak 30-‐35 dakika kadar pişirdikten sonra fırından alın ve birazdemlenmesini bekledikten sonra servis yapın.

Algoritma

¨ Kekin yapımı:• Fırını 180 dereceye getir.• Bir kap al.• Kabın içine 3 yumurtayı kır ve 2 çay bardağı toz şeker koy• WHILE (köpürmedi)

yumurta ve toz şekeri çırp• Diğer bütün malzemeleri (2 çay bardağı yoğurt, yarım su bardağı zeytinyağı,

1 paket kabartma tozu, 1 paket vanilin, 3 su bardağı un) kabın içine koy• Bütün harcı bir kalıba dök.• Kalıbı fırına koy• WHILE (kek pişmedi)

Kalıbı fırında tut.• Keki fırından çıkar.

Bir Algoritmanın Geliştirilmesi

¨ Bir problemi çözmede bilgisayar çözümü üretmenin iki yöntemivardır:¤ Yukarıdan aşağı tasarım (Top-down design)

n Yapılacak görevlere yoğunlaşır.¤Nesneye yönelik tasarım (Object-oriented design)

nVeriye yoğunlaşır.

Algoritmaları ifade etmek için yalancı kodlar kullanılır!

Yukarıdan-Aşağı Tasarım

Yalancı Kod

¨ Yalancı kod (pseudocode): İngilizceifadelerle programlama dili ifadelerininkarışık bir şekilde kullanıldığı kodlar.

¨ Örnek:10’luk tabandaki bir sayının başka bir tabanaçevrilmesi:

While (the quotient is not zero)Divide the decimal number by the new baseMake the remainder the next digit to the left in the answerReplace the original decimal number with the quotient

While (bölüm sıfır değil)Yeni ondalıklı sayıyı yeni tabana bölKalanı sola doğru bir sonraki basamak yapOrjinal ondalıklı sayıyı bölümle yer değiştir.

Yalancı Kod

Ondalık tabanda 93’ün 8’lik tabandaki karşılığı nedir?93/8’in sonucu 11, kalan 5’tir.11/8’nın sonucu 1, kalan 3’tür.1/ 8’in sonucu 0, kalan 1’dir.

sonuç: 1 3 5

While (bölüm sıfır değil)Yeni ondalıklı sayıyı yeni tabana bölKalanı sola doğru bir sonraki basamak yapOrjinal ondalıklı sayıyı bölümle yer değiştir.

Tam Çözüm için Yalancı KodYazdır: “Yeni tabanı giriniz"Oku: yeniTabanYazdır: “Çevrilecek sayıyı giriniz"Oku: ondalıkSayıBölümü 1 olarak kaydet.WHILE (bölüm 0 değil)

Bölüme ondalıkSayi/yeniTaban değerini ataKalana ondalıkSayi % yeniTaban değerini ataKalanı sola doğru bir basamak olarak kaydet.ondalıkSayı değerini bölüm olarak güncelle

Yazdır: “Sonuç: "Sonucu yazdır

Yalancı Koddaki İfadeler

¨ Değişkenler:¤ Verilerin kaydedildiği depo alanları

n Örnek: bölüm, ondalıkSayı, yeniTaban

¨ Atama ifadeleri:¤ Bir değişkene yeni değer verme

n Bölüme 64 değerini ata.

Yalancı Koddaki İfadeler

¨ Çıktı¤ Bir çıktı aygıtına değerin yazdırılması:

n Yazdır (Write, Print)

¨ Girdi¤Dış dünyadan değerlerin alınıp değişkenlere kaydedilmesi

n Oku (Get, Read)

Kontrol Yapıları

¨ Kontrol yapısı:¤ Programda komutların hangi sırada çalıştırılacağını belirleyenkomuttur.

Seçim İfadeleri¨ Seçim:

¤ Farklı ifadelerin içinden birini çalıştırmak için seçmek veyabazı ifadeleri atlamak için kullanılır.

Sayıyı alIF (sayı < 0)

Yazdır sayı + " 0’dan küçüktür."veyaYazdır ”Pozitif bir sayı giriniz."

Sayıyı alIF(sayı < 0)

Yazdır sayı + " 0’dan küçüktür."Yazdır ”Talimatlara uymadınız."

Seçim İfadeleri

à if deyimi

Seçim İfadeleri

• Problem: Verilen bir hava sıcaklığına göre uygun kıyafeti yazdır.

Yazdır: “Sıcaklık değerini girin: "Sıcaklık değerini al.Kıyafeti belirle.

Seçim İfadeleri

IF (sicaklik > 90)Yazdır “Hava sıcak: şort giy.”

ELSE IF (sicaklik > 70)Yazdır “ideal hava: Kısa kollu t-‐shirt giymek uygundur.”

ELSE IF (sicaklik > 50)Yazdır “Biraz serin: ince bir ceket giy.”

ELSE IF (sicaklik > 32)Yazdır “Oldukça soğuk: Kalın bir mont giy.”

ELSEYazdır “İçeride kal.”

Kıyafeti Belirle

Döngü İfadeleri

¨ Tekrar:¤ Bir dizi ifadenin tekrar edilmesi.

Set count to 1WHILE ( count < 10)

Write "Enter an integer number"Read aNumberWrite "You entered " + aNumberSet count to count + 1

Kaç değer okunur?

Döngü İfadeleri

àwhile ifadesi

Döngü İfadeleri

Toplama 0 değerini ver.Sayaca 1 değerini ver.While (sayac <= limit)

Sayıyı okuToplama, toplam+sayı değerini ata.Sayacı artır

Yazdır: “Toplam:" + toplam

Neden sayaç kontrollüdeyim deniyor?

Sayaç kontrollü döngü:

Döngü İfadeleri

Toplama 0 değerini ver.Pozitif değişkenine ‘dogru’ değerini verWHILE (Pozitif)

Sayı okuIF (Sayı > 0)

Toplama toplam+sayı değerini ver.ELSE

Pozitif’e yanlış değerini ver.Yazdır: ”Toplam" + toplam

Neden olay kontrollüdöngü deniyor?

Buradaki olay nedir?

Olay kontrollü deyim:

Yalancı Kod Örneği

Problem: Tekrarlı bir şekilde bir çift sayı al vedeğerleri yazdır.

WHILE (not done)Write "Enter two values separated by blanks"Read number1Read number2

Print them in order

Yalancı Kod Örneği

Write "How many pairs of values are to be entered?"Read numberOfPairsSet numberRead to 0WHILE (numberRead < numberOfPairs)

Write "Enter two values separated by a blank;; press return"Read number1Read number2IF(number1 < number2)

Print number1 + " " + number2ELSE

Print number2 + " " number1Increment numberRead

Değerleri sırayla yazdır:

Yalancı Kodun Çevrilmesi

• Hangi dile çevrilecek?Assembly dili

Çok ayrıntılı ve zaman alır.

Üst düzey programlama dili

Yazması daha kolay.


33

From problem to program

¨ In “real world”… • Problem in Natural language• Top Down Design in pseudo-code• Program in computer code

(code in almost any computer language.)

Requirements:

A program that does this and that and theother. It must take data fromthis source and

IMPLEMENTReduce cognitive load• separating design and coding• using top-down design

The Problem

Do thisrepeatif something thendo this

elsedo the other

Print “all done”

DESIGN

The Design(Algorithm)

The Program


34

Steps of Software Development

1. Problem Understanding¤ Read the problem carefully and try to understand what is required for its solution.

2. Analysis¤ Identify problem inputs and outputs.

3. Design¤ Develop a list of steps (algorithm) to solve the problem¤ Refine steps of this algorithm. (Divide and Conquer)¤ Verify that the algorithm solves the problem, i.e. the algorithm is correct.

4. Implementation¤ Implement the algorithm as a (java) program.¤ You have to know a specific programming language (java)¤ Convert steps of the algorithm into programming language statements.

5. Testing and Verification¤ Test the completed program, and verify that it works as expected.¤ Use different test cases (not one) including critical test cases.


35

Algorithm

¨ An algorithm is a design written in pseudo code. (in English, but a formal style)

¨ Algorithms contain:¤ Sequence¤ Decision¤ Repetition


36

Everyday Algorithms Problem: To drink a glass of milk.

Algorithm:1. Enter the kitchen2. Get a glass3. Get the milk from the refrigerator4. Fill the glass with milk5. Drink it

Refine step 1:1. Walk to the kitchen door2. If the door is close then2.T. Open it3. Walk into the kitchen

Refine step 3:1. Open the refrigerator2. Get the milk3. Close the refrigerator

Refine step 4:1. while the glass is not full

1.1. Pour some milk into the glass


37

Area-‐Circumference Problem

Requirements:Design an algorithm to find and report the area andcircumference of a circle whose radius the user gives.

Welcome to circle computer…

Please enter the radius: 5

The area of a circle of radius 5 is 78.55

and its circumference is 31.42

Example interaction


38

Area-‐Circumference ProblemTo find area & circumference of circle…

1. Print welcome message2. Ask for & get radius from user3. Compute area as pi.radius.radius4. Compute circumference as 2.pi.radius5. Report area, circumference & radius

Identify preconditions & ensure they are satisfied.

Once we are sure that this is correct, move on to solve any non-

trivial sub-problems.


39

Area-‐Circumference Problem (cont.)

Solve…5. Report area, circumference & radius

1. Print msg “The area of a circle with radius ”

2. Print radius value3. Print msg “ is ”4. Print area value and move to next

line5. Print msg “ and its circumference

is ”6. Print circumference value7. Print blank line

Solve…2. Ask for & get radius from user

1. Ask (prompt) the user to enter radius

2. Get radius value from user


40

Calculating the average score of an exam

Problem: Calculating the average score of an exam

Inputs : Scores of an examOutput: Average score of the exam

Algorithm:1. Set count to zero2. Set sum to zero3. while there is an exam sheet do

3.1. Read the score on the sheet3.2. Add the score on the sheet to sum3.3. Add one to count3.4. Move to the next sheet

4. Compute average as sum/count5. Display average


41

Prime NumberProblem: Deciding that a given integer number is prime or not.Input : An integer number NOutput: A sentence indicating that N is prime or not.

Algorithm:1. Read the number N2. Test whether N is prime or not3. Display the result.

Refine step 2:1. set counter to 22. set PrimeFlag to true3. while (counter < N and PrimeFlag = true) do3.1. if N is divisible by counter then

3.1.T. set PrimeFlag to false3.2. Increment counter by 1

Refine step 3:1. if PrimeFlag = true then1.T. Display that N is prime

else1.F. Display that N is not prime


42

Factorial

Problem: Calculating N!Inputs: A positive integer NOutput: N!

Algorithm:1. Read a positive integer N2. Calculate NFactorial3. Display NFactorial

Refine step 2:1. Set NFactorial to 12. Set counter to 23. while (counter <= N) do3.1. Multiply NFactorial by counter3.2. Increment counter by 1


43

Types & Layout (of algorithm steps)

n. dostep

while condition

indent

1. step 2. step3. step4. step

Sequence

n. if condition thennT step

elsenF step

indent

Decision

n. while condition dostep

indent

Repetition

Any step can be replaced with one of the other

types

n. for so many times dostep

Documents

BBS#514 YAPISAL#PROGRAMLAMA …burcucan/BBS514... · 2017-10-04 · BBS65146TYapısal6Programlama6(Structured6Programming) 39 AreaTCircumference6Problem(cont.) Solve… 5. Report