ლექცია 10, State Machines

problem 9.9

ეს უფრო პროგრამირებაა და არ მოვა. სწრაფი ახარისხების პროგრამაა.

problem 9.2

დაფაზე წერია ორი რიცხვი. 2 მოთამაშეა. რიგ-რიგობით წერენ ახალ რიცხვს, რომელიც უნდა მიიღონ დაწერილი რიცხვების სხვაობით. ვინც ვეღარ დაწერს ახალ რიცხვს, აგებს.

ა) დაამტკიცეთ რომ თამაშის ბოლოს ყველა რიცხვი იქნება პირველი ორი რიცხვის უსგ-ს ჯერადი.
ბ)აჩვენეთ რომ ყველა დადებითი ჯერადი უსგ-სი (პირველი ორი რიცხვიდან უდიდესზე მცირე) იქნება დაფაზე დაწერილი თამაშის ბოლომდე.
გ)აღწერეთ სტრატეგია, რომელიც მოგვაგებინებს ყოველ თამაშს.

ა)ეს რიცხვები იყოს a და b. ვწერთ ყველა რიცხვს, რომელიც მათი სხვაობით მიიღება. დავუშვათ რომელიმე მათგანი არაა მათი უსგ-ს ჯერადი. მათ შორის პირველი იყოს x. x-მდე რაც დავწერეთ, ყველაფერი არის a-სა და b-s უსგ. გამოდის, რომ x-ის მისაღებად, ერთ უსგ-ს ჯერადს ვაკლებთ მეორე უსგ-ს:
x= უსგ*y'-უსგ*y''= უსგ*(y'-y'').
გამოვიდა, რომ x არის უსგ-ს ჯერადი.

ბ) ჯერ დავამტკიცოთ, რომ მივალთ უსგ - მდე.
ჩვენ შეგვიძლია ჩავიდეთ უსგ-მდე, ევკლიდეს ალგორითმით, გამოვსახოთ ჩვენს მიერ მიღებული რიცხვები ბიჯებად:
a b
c1
c2
c3
....
x - სადაც x არის უსგ.
თამაშშიც გავივლით თითოეულ ნაბიჯს, თუ გვაქვს a და b აუცილებლად უნდა მივიღოთ с1 შემდეგ с2 და ასე შემდეგ x.

problem 9.12

მაგიდაზე გვაქვს 102 ხურდა. 98 არიოლით ზევით, 4 - რეშკით. გვაქვს 2 მოქმედება:
1)გადავაბრუნოთ ნებისმიერი 10 ხურდა.
2)n იყოს არიოლების რაოდენობა. დავდოთ მაგიდაზე n+1 ხურდა, თითოეული რეშკით ზევით.

ა)აღწერეთ ამოცანის state machine
ბ)აღწერეთ, როგორ მივაღწიოთ სიტუაციას, როცა ზუსტად 1 რეშკა გვექნება.
გ)აღწერეთ შემდეგი ცვლადები:
C - ხურდების რაოდენობა მაგიდაზე
H - არიოლების რაოდენობა
T - რეშკების რაოდენობა
C2- ნაშთი C/2-ის
H2- ნაშთი H/2-ის
T2 - ნაშთი T/2-ის

რომელი მათგანი:

1. მკაცრად იზრდება
2. არამკაცრად იზრდება
3. მკაცრად მცირდება
4. არამკაცრად მცირდება
5. მუდმივია

დ)დაამტკიცეთ, რომ ვერ მივაღწევთ მდგომარეობას, როცა მხოლოდ ერთი არიოლი გვაქვს.

//amoxsna iqneba

problem 9.13
ამოცანა დაავადებულ სტუდენტებზე.

შემოვიღოთ ცნება P - დაავადებულ სტუდენთა "საზღვართა" ჯამი.
თავდაპირველად მაქსიმალური საზღვარი არის 4*k, თუ k ნაკლებია n-ზე. ახლა დავამტკიცოთ, რომ საზღვარი არ იზრდება. არის 3 ვარიანტი:
"დასაავადებელ" სტუდენტს ესაზღვრება 2,3 ან 4 დაავადებული სტუდენტი.

• თუ 2 ესაზღვრება, მისი დაავადების შედეგად, 2 საზღვარი წაიშლება, 2 დაემატება და ჯამში იგივე დარჩება.
• თუ 3 ესაზღვრება, 3 გამოაკლდება, 1 დაემატება, ჯამში 2 დააკლდება.
• თუ 4 ესაზღვრება, 4 გამოაკლდება.

გამოდის, რომ 4*k არ იზრდება. მიზანია 4*n მივიღოთ. 4*k მაქსიმუმ არის 4*(n-1).