USE 2017-ის მე-2 დავალების ანალიზი კომპიუტერულ მეცნიერებაში დემო პროექტიდან. ეს არის ძირითადი დონის ამოცანა. დავალების შესრულების სავარაუდო დროა 3 წუთი.
შემოწმებული შინაარსის ელემენტები: სიმართლის ცხრილების და ლოგიკური სქემების აგების შესაძლებლობა. გამოცდაზე გამოცდილი შინაარსის ელემენტები: განცხადებები, ლოგიკური ოპერაციები, რაოდენობები, განცხადების სიმართლე.
დავალება 2:
ლოგიკური ფუნქცია ფგამოთქმით მოცემული x /\¬ წ /\ (¬ ზ \/ ვ).
ფიგურაში ნაჩვენებია ფუნქციის სიმართლის ცხრილის ფრაგმენტი ფ, შეიცავს ყველა ფმართალია.
დაადგინეთ ფუნქციის სიმართლის ცხრილის რომელი სვეტი ფშეესაბამება თითოეულ ცვლადს ვ, x, წ, ზ.
ჩაწერეთ ასოები თქვენს პასუხში. w, x, y, zთანმიმდევრობით, რომლითაც მიდის მათ შესაბამისი სვეტები (ჯერ - პირველი სვეტის შესაბამისი ასო; შემდეგ - მეორე სვეტის შესაბამისი ასო და ა.შ.) დაწერეთ ასოები პასუხში ზედიზედ, ასოებს შორის გამყოფი არ არის. საჭირო.
მაგალითი. თუ ფუნქცია მოცემულია გამოსახულებით ¬ x \/ წდამოკიდებულია ორ ცვლადზე: xდა წდა მიეცა ფრაგმენტი მისი სიმართლის ცხრილიდან, რომელიც შეიცავს ყველაარგუმენტების კომპლექტი, რომლისთვისაც ფუნქცია ფმართალია.
მაშინ პირველი სვეტი შეესაბამება ცვლადს წდა მეორე სვეტი არის ცვლადი x. პასუხი უნდა ყოფილიყო: yx.
პასუხი: ________
x /\¬ წ /\ (¬ ზ \/ ვ)
კავშირი (ლოგიკური გამრავლება) მართალია, თუ და მხოლოდ მაშინ, თუ ყველა დებულება ჭეშმარიტია. აქედან გამომდინარეობს ცვლადი X 1 .
ასე რომ, ცვლადი xშეესაბამება სვეტს ცვლადით 3.
ცვლადი ¬yუნდა ემთხვეოდეს სვეტს, რომელშიც არის მნიშვნელობა 0 .
ორი დებულების დისუნქცია (ლოგიკური დამატება) მართალია, თუ და მხოლოდ მაშინ, თუ ერთი დებულება მაინც არის ჭეშმარიტი.
დისჯუნქცია ¬z \/wამ სტრიქონში მართალი იქნება მხოლოდ იმ შემთხვევაში z=0, w=1.
ასე რომ, ცვლადი ¬ზშეესაბამება სვეტს ცვლად 1-თან (1 სვეტი), ცვლადი ვშეესაბამება სვეტს ცვლადით 4 (სვეტი 4).
№1
(x /\ y/\z/\¬w)\/ (x /\ y/\¬z/\¬w)\/ (x /\¬y/\¬z/\¬w).
გადაწყვეტილება
x /\ y/\z/\¬w – x=1, y=1, z=1, w=0;
x /\ y/\¬z/\¬w – x=1, y=1, z=0, w=0;
x /\¬y/\¬z/\¬w – x=1, y=0, z=0, w=0.
შედეგად ვიღებთ 6 ერთეულს.
პასუხი:
6.
№2 ლოგიკური ფუნქცია F მოცემულია გამოსახულებით
(¬x /\ y/\¬z/\w)\/ (x /\ y/\z/\¬w)\/ (x /\¬ y/\¬z/\w).
სტეპანმა ჩაწერა ცვლადების ყველა ნაკრები, რომლებისთვისაც ეს გამოთქმა მართალია. რამდენი ერთეული დაწერა სტეპანმა? პასუხში ჩაწერეთ მხოლოდ მთელი რიცხვი - ერთეულების რაოდენობა.
მაგალითი. მიეცით გამოხატულება x → y ორ x და y ცვლადზე დამოკიდებული. ეს გამოთქმა მართალია სამი ნაკრებისთვის: (0, 0), (0, 1) და (1, 1). სტეპანმა დაწერა 3 ერთეული.
გადაწყვეტილება ხსნარის მსგავსი.
№3 ლოგიკური ფუნქცია F მოცემულია გამოსახულებით
(x /\ ¬y/\z/\w)\/ (x /\ y/\¬z/\w)\/ (¬x /\ y/\ z/\w).
სტეპანმა ჩაწერა ცვლადების ყველა ნაკრები, რომლებისთვისაც ეს გამოთქმა მართალია. რამდენი ერთეული დაწერა სტეპანმა? პასუხში ჩაწერეთ მხოლოდ მთელი რიცხვი - ერთეულების რაოდენობა.
მაგალითი. მიეცით გამოხატულება x → y ორ x და y ცვლადზე დამოკიდებული. ეს გამოთქმა მართალია სამი ნაკრებისთვის: (0, 0), (0, 1) და (1, 1). სტეპანმა დაწერა 3 ერთეული.
გადაწყვეტილება ხსნარის მსგავსი.
№4 ლოგიკური ფუნქცია F მოცემულია გამოსახულებით
(¬x /\ ¬y/\z/\w)\/ (¬x /\ ¬y/\¬z/\w)\/ (¬x /\ y/\ z/\¬w).
სტეპანმა ჩაწერა ცვლადების ყველა ნაკრები, რომლებისთვისაც ეს გამოთქმა მართალია. რამდენი ერთეული დაწერა სტეპანმა? პასუხში ჩაწერეთ მხოლოდ მთელი რიცხვი - ერთეულების რაოდენობა.
მაგალითი. მიეცით გამოხატულება x → y ორ x და y ცვლადზე დამოკიდებული. ეს გამოთქმა მართალია სამი ნაკრებისთვის: (0, 0), (0, 1) და (1, 1). სტეპანმა დაწერა 3 ერთეული.
გადაწყვეტილება ხსნარის მსგავსი.
№5 ლოგიკური ფუნქცია F მოცემულია გამოსახულებით
(¬x /\ y/\¬z/\¬w)\/ (x /\ ¬y/\¬z/\¬w)\/ (¬x /\ ¬y/\ z/\¬w).
სტეპანმა ჩაწერა ცვლადების ყველა ნაკრები, რომლებისთვისაც ეს გამოთქმა მართალია. რამდენი ერთეული დაწერა სტეპანმა? პასუხში ჩაწერეთ მხოლოდ მთელი რიცხვი - ერთეულების რაოდენობა.
მაგალითი. მიეცით გამოხატულება x → y ორ x და y ცვლადზე დამოკიდებული. ეს გამოთქმა მართალია სამი ნაკრებისთვის: (0, 0), (0, 1) და (1, 1). სტეპანმა დაწერა 3 ერთეული.
გადაწყვეტილება ხსნარის მსგავსი.
№6 ლოგიკური ფუნქცია F მოცემულია გამოსახულებით
(x /\ y/\¬w)\/ (x /\¬y/\¬z/\¬w).
სტეპანმა ჩაწერა ცვლადების ყველა ნაკრები, რომლებისთვისაც ეს გამოთქმა მართალია. რამდენი ერთეული დაწერა სტეპანმა? პასუხში ჩაწერეთ მხოლოდ მთელი რიცხვი - ერთეულების რაოდენობა.
მაგალითი. მიეცით გამოხატულება x → y ორ x და y ცვლადზე დამოკიდებული. ეს გამოთქმა მართალია სამი ნაკრებისთვის: (0, 0), (0, 1) და (1, 1). სტეპანმა დაწერა 3 ერთეული.
გადაწყვეტილება
ლოგიკური ფუნქცია F არის ჭეშმარიტი, თუ ფრჩხილებში ერთი გამოხატულება მაინც არის ჭეშმარიტი. ვინაიდან მათში ყველა ცვლადი დაკავშირებულია კავშირით, მაშინ თითოეული ტერმინი უნდა იყოს ჭეშმარიტი. მოდით ჩამოვწეროთ ჭეშმარიტი კომპლექტები თითოეული დისუნქციისთვის.
x /\ y/\¬w – (x=1, y=1, z=1, w=0) და (x=1, y=1, z=0, w=0);
x /\¬y/\¬z/\¬w – x=1, y=1, z=0, w=0.
შედეგად ვიღებთ 6 ერთეულს.
№7 ლოგიკური ფუნქცია F მოცემულია გამოსახულებით
(x /\ y/\z/\¬w)\/ (x /\¬z/\¬w).
სტეპანმა ჩაწერა ცვლადების ყველა ნაკრები, რომლებისთვისაც ეს გამოთქმა მართალია. რამდენი ერთეული დაწერა სტეპანმა? პასუხში ჩაწერეთ მხოლოდ მთელი რიცხვი - ერთეულების რაოდენობა.
მაგალითი. მიეცით გამოხატულება x → y ორ x და y ცვლადზე დამოკიდებული. ეს გამოთქმა მართალია სამი ნაკრებისთვის: (0, 0), (0, 1) და (1, 1). სტეპანმა დაწერა 3 ერთეული.
გადაწყვეტილება ხსნარის მსგავსი.
№8 ლოგიკური ფუნქცია F მოცემულია გამოსახულებით
(¬x /\ ¬y/\z/\w)\/ (x /\z/\w).
სტეპანმა ჩაწერა ცვლადების ყველა ნაკრები, რომლებისთვისაც ეს გამოთქმა მართალია. რამდენი ერთეული დაწერა სტეპანმა? პასუხში ჩაწერეთ მხოლოდ მთელი რიცხვი - ერთეულების რაოდენობა.
მაგალითი. მიეცით გამოხატულება x → y ორ x და y ცვლადზე დამოკიდებული. ეს გამოთქმა მართალია სამი ნაკრებისთვის: (0, 0), (0, 1) და (1, 1). სტეპანმა დაწერა 3 ერთეული.
გადაწყვეტილება ხსნარის მსგავსი.
№9 ლოგიკური ფუნქცია F მოცემულია გამოსახულებით
(y /\ ¬z /\ ¬w) \/ (¬x /\ ¬y/\¬z/\w).
სტეპანმა ჩაწერა ცვლადების ყველა ნაკრები, რომლებისთვისაც ეს გამოთქმა მართალია. რამდენი ერთეული დაწერა სტეპანმა? პასუხში ჩაწერეთ მხოლოდ მთელი რიცხვი - ერთეულების რაოდენობა.
მაგალითი. მიეცით გამოხატულება x → y ორ x და y ცვლადზე დამოკიდებული. ეს გამოთქმა მართალია სამი ნაკრებისთვის: (0, 0), (0, 1) და (1, 1). სტეპანმა დაწერა 3 ერთეული.
გადაწყვეტილება ხსნარის მსგავსი.
№10 ლოგიკური ფუნქცია F მოცემულია გამოსახულებით
(x /\ y /\ ¬z) \/ (¬x /\ ¬y/\¬z).
სტეპანმა ჩაწერა ცვლადების ყველა ნაკრები, რომლებისთვისაც ეს გამოთქმა მართალია. რამდენი ერთეული დაწერა სტეპანმა? პასუხში ჩაწერეთ მხოლოდ მთელი რიცხვი - ერთეულების რაოდენობა.
მაგალითი. მიეცით გამოხატულება x → y ორ x და y ცვლადზე დამოკიდებული. ეს გამოთქმა მართალია სამი ნაკრებისთვის: (0, 0), (0, 1) და (1, 1). სტეპანმა დაწერა 3 ერთეული.
გადაწყვეტილება ხსნარის მსგავსი.
№11 ლოგიკური ფუნქცია F მოცემულია გამოსახულებით
¬((¬w/\x) → (y /\ z)) \/ ¬((x /\¬ y)→ (¬z\/¬w)).
სტეპანმა ჩაწერა ცვლადების ყველა ნაკრები, რომლებისთვისაც ეს გამოთქმა მართალია. რამდენი ერთეული დაწერა სტეპანმა? პასუხში ჩაწერეთ მხოლოდ მთელი რიცხვი - ერთეულების რაოდენობა.
მაგალითი. მიეცით გამოხატულება x → y ორ x და y ცვლადზე დამოკიდებული. ეს გამოთქმა მართალია სამი ნაკრებისთვის: (0, 0), (0, 1) და (1, 1). სტეპანმა დაწერა 3 ერთეული.
გადაწყვეტილება
¬((¬w/\x) → (y /\ z)) – (x=1, y=1, z=0, w=0) და (x=1, y=0, z=1, w =0);
¬((x /\¬y)→ (¬z\/¬w)) – (x=1, y=0, z=1, w=1).
შედეგად ვიღებთ 5 ერთეულს.
№12 ლოგიკური ფუნქცია F მოცემულია გამოსახულებით
¬((¬x\/¬y) → (z \/ w)) \/ ¬((x \/ y)→ (z\/¬w)).
სტეპანმა ჩაწერა ცვლადების ყველა ნაკრები, რომლებისთვისაც ეს გამოთქმა მართალია. რამდენი ერთეული დაწერა სტეპანმა? პასუხში ჩაწერეთ მხოლოდ მთელი რიცხვი - ერთეულების რაოდენობა.
მაგალითი. მიეცით გამოხატულება x → y ორ x და y ცვლადზე დამოკიდებული. ეს გამოთქმა მართალია სამი ნაკრებისთვის: (0, 0), (0, 1) და (1, 1). სტეპანმა დაწერა 3 ერთეული.
გადაწყვეტილება
ლოგიკური ფუნქცია F არის ჭეშმარიტი, თუ ფრჩხილებში ერთი გამოხატულება მაინც არის ჭეშმარიტი. ვინაიდან მათში არსებული ყველა ცვლადი გულისხმობს, მაშინ მისი სიცრუის პირობა იძლევა ფრჩხილების ჭეშმარიტებას. მაგალითის შემდეგ, ჩვენ ვწერთ ჭეშმარიტ სიმრავლეებს თითოეული ფრჩხილისთვის.
¬((¬x\/¬y) → (z \/ w)) – (x=1, y=0, z=0, w=0) და (x=0, y=1, z=0, w=0);
¬((x /\¬y)→ (¬z\/¬w)) – (x=1, y=0, z=0, w=0).
შედეგად ვიღებთ 3 ერთეულს.
№13 ლოგიკური ფუნქცია F მოცემულია გამოსახულებით
¬(¬(x\/y) → (¬z\/ w)) \/ ¬(¬(x /\ y)→ (z\/¬w)).
სტეპანმა ჩაწერა ცვლადების ყველა ნაკრები, რომლებისთვისაც ეს გამოთქმა მართალია. რამდენი ერთეული დაწერა სტეპანმა? პასუხში ჩაწერეთ მხოლოდ მთელი რიცხვი - ერთეულების რაოდენობა.
მაგალითი. მიეცით გამოხატულება x → y ორ x და y ცვლადზე დამოკიდებული. ეს გამოთქმა მართალია სამი ნაკრებისთვის: (0, 0), (0, 1) და (1, 1). სტეპანმა დაწერა 3 ერთეული.
გადაწყვეტილება
ლოგიკური ფუნქცია F არის ჭეშმარიტი, თუ ფრჩხილებში ერთი გამოხატულება მაინც არის ჭეშმარიტი. ვინაიდან მათში არსებული ყველა ცვლადი გულისხმობს, მაშინ მისი სიცრუის პირობა იძლევა ფრჩხილების ჭეშმარიტებას. მაგალითის შემდეგ, ჩვენ ვწერთ ჭეშმარიტ სიმრავლეებს თითოეული ფრჩხილისთვის.
¬(¬(x\/y) → (¬z\/ w)) – (x=0, y=0, z=1, w=0);
¬(¬(x /\ y)→ (z\/¬w)) – (x=1, y=0, z=0, w=1), (x=0, y=1, z=0, w=1) და
(x=0, y=0, z=0, w=1).
შედეგად ვიღებთ 6 ერთეულს.
ლოგიკური ფუნქცია ფგამოთქმით მოცემული x/\ ¬y/\ (¬ზ\/ ვ).
ფიგურაში ნაჩვენებია ფუნქციის სიმართლის ცხრილის ფრაგმენტი ფ, შეიცავს ყველაარგუმენტების კომპლექტი, რომლისთვისაც ფუნქცია ფმართალია.
დაადგინეთ ფუნქციის სიმართლის ცხრილის რომელი სვეტი ფშეესაბამება თითოეულ ცვლადს ვ, x, წ, ზ.
ჩაწერეთ ასოები თქვენს პასუხში. ვ, x, წ, ზთანმიმდევრობით ისინი მიდიან
მათ შესაბამისი სვეტები (პირველი - პირველის შესაბამისი ასო
სვეტი შემდეგ – მეორე სვეტის შესაბამისი ასო და სხვ.) ასოები
პასუხში ჩაწერეთ ზედიზედ, ასოებს შორის გამყოფები არ ჩადეთ
არ არის საჭირო.
2017 წლის ერთიანი სახელმწიფო გამოცდის დემო ვერსია - დავალება No2
გადაწყვეტილება:
კავშირი (ლოგიკური გამრავლება) მართალია, თუ და მხოლოდ მაშინ, თუ ყველა დებულება ჭეშმარიტია. აქედან გამომდინარეობს ცვლადი X 1 .
ცვლადი ¬yუნდა ემთხვეოდეს სვეტს, რომელშიც ყველა მნიშვნელობა ტოლია 0 .
ორი დებულების დისუნქცია (ლოგიკური დამატება) მართალია, თუ და მხოლოდ მაშინ, თუ ერთი დებულება მაინც არის ჭეშმარიტი.
დისჯუნქცია ¬z \/ y z=0, w=1.
ასე რომ, ცვლადი ¬ზ ვშეესაბამება სვეტს ცვლადით 4 (სვეტი 4).
პასუხი: zyxw
2016 წლის ერთიანი სახელმწიფო გამოცდის დემო ვერსია - დავალება No2
ლოგიკური ფუნქცია ფმოცემული (¬z)/\x \/ x/\y-ით. დაადგინეთ F ფუნქციის სიმართლის ცხრილის რომელი სვეტი შეესაბამება თითოეულ ცვლადს x, y, z.
თქვენს პასუხში ჩაწერეთ ასოები x, y, z იმ თანმიმდევრობით, რომლითაც მიდის მათ შესაბამისი სვეტები (ჯერ - 1-ლი სვეტის შესაბამისი ასო; შემდეგ - მე-2 სვეტის შესაბამისი ასო; შემდეგ - ასო. მე-3 სვეტი). პასუხში ასოები ზედიზედ ჩაწერეთ, ასოებს შორის გამყოფების დადება არ გჭირდებათ.
მაგალითი. მიეცით გამოხატულება x → y, რომელიც დამოკიდებულია ორ x და y ცვლადზე და სიმართლის ცხრილზე:
შემდეგ 1 სვეტი შეესაბამება y ცვლადს, ხოლო მე-2 სვეტს
შეესაბამება x-ს. პასუხში უნდა დაწეროთ: yx.
გადაწყვეტილება:
1. დაწერეთ ამისთვის მოცემული გამოხატულებაუფრო მარტივი ნოტაციით:
¬z*x + x*y = x*(¬z + y)
2. კავშირი (ლოგიკური გამრავლება) მართებულია, თუ და მხოლოდ მაშინ, თუ ყველა დებულება ჭეშმარიტია. ამიტომ, იმისათვის, რომ ფუნქცია ( ფ) უდრის ერთს ( 1 ), აუცილებელია, რომ თითოეული მულტიპლიკატორი იყოს ერთის ტოლი ( 1 ). ამრიგად, ზე F=1, ცვლადი Xუნდა ემთხვეოდეს სვეტს, რომელშიც ყველა მნიშვნელობა ტოლია 1 .
3. განიხილეთ (¬z + y), ზე F=1ეს გამოთქმა ასევე უდრის 1-ს (იხ. პუნქტი 2).
4. ორი დებულების დისიუქცია (ლოგიკური დამატება) მართალია, თუ და მხოლოდ მაშინ, თუ ერთი დებულება მაინც არის ჭეშმარიტი.
დისჯუნქცია ¬z \/ yამ სტრიქონში მართალი იქნება მხოლოდ იმ შემთხვევაში
- z = 0; y=0ან y=1;
- z = 1; y=1
5. ცვლადი გზა ¬ზშეესაბამება სვეტს ცვლად 1-თან (1 სვეტი), ცვლადი წ
პასუხი: zyx
KIM ერთიანი სახელმწიფო გამოცდა USE 2016 (ადრეული პერიოდი)- დავალება ნომერი 2
ლოგიკური ფუნქცია F მოცემულია გამოსახულებით
(x /\ y /\¬z) \/ (x /\ y /\ z) \/ (x /\¬y /\¬z).
სურათზე ნაჩვენებია F ფუნქციის სიმართლის ცხრილის ფრაგმენტი, რომელიც შეიცავს არგუმენტების ყველა კომპლექტს, რომლისთვისაც ფუნქცია F არის ჭეშმარიტი. დაადგინეთ F ფუნქციის სიმართლის ცხრილის რომელი სვეტი შეესაბამება x, y, z თითოეულ ცვლადს.
თქვენს პასუხში ჩაწერეთ ასოები x, y, z იმ თანმიმდევრობით, რომლითაც გამოჩნდება მათი შესაბამისი სვეტები (ჯერ - პირველი სვეტის შესაბამისი ასო; შემდეგ - მეორე სვეტის შესაბამისი ასო და ა.შ.) დაწერეთ ასოები. ზედიზედ პასუხში, ასოებს შორის გამყოფები არ არის საჭირო.
რ გამოსავალი:
მოდით ჩავწეროთ მოცემული გამოხატულება უფრო მარტივი აღნიშვნით:
(x*y*¬z) + (x*y*z) + (x*¬y*¬z)=1
ეს გამონათქვამი მართალია, თუ (x*y*¬z) , (x*y*z) , (x*¬y*¬z) ერთი მაინც უდრის 1-ს. კავშირი (ლოგიკური გამრავლება) მართალია, თუ და მხოლოდ იმ შემთხვევაში, როდესაც ყველა განცხადება მართალია.
ერთ-ერთი მაინც ამ დისკუსიებიდან x*y*¬z; x*y*z; x*¬y*¬zმართალი იქნება მხოლოდ იმ შემთხვევაში x=1.
ასე რომ, ცვლადი Xშეესაბამება სვეტს ცვლადით 2 (სვეტი 2).
დაე იყოს y- var.1, z-პრემია 3. შემდეგ, პირველ შემთხვევაში x*¬y*¬zმართალი იქნება მეორე შემთხვევაში x*y*¬zდა მესამეში x*y*z.
პასუხი: yxz
სიმბოლო F აღნიშნავს ერთ-ერთ შემდეგს ლოგიკური გამონათქვამებისამი არგუმენტიდან: X, Y, Z. მოცემულია F გამოთქმის სიმართლის ცხრილის ფრაგმენტი (იხ. ცხრილი მარჯვნივ). რა გამოთქმა შეესაბამება F-ს?
| X | ი | ზ | ფ |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
1) X ∧ Y ∧ Z 2) ¬X ∨ Y ∨¬Z 3) X ∧ Y ∨ Z 4) X ∨ Y ∧ ¬Z
გადაწყვეტილება:
1) X ∧ Y ∧ Z = 1.0.1 = 0 (არ ემთხვევა მე-2 ხაზს)
2) ¬X ∨ Y ∨¬Z = ¬0 ∨ 0 ∨ ¬0 = 1+0+1 = 1 (არ ემთხვევა 1-ელ ხაზს)
3) X ∧ Y ∨ Z = 0.1+0 = 0 (არ ემთხვევა მე-3 ხაზს)
4) X ∨ Y ∧ ¬Z (შეესაბამება F)
X ∨ Y ∧ ¬Z = 0 ∨ 0 ∧ ¬0 = 0+0.1 = 0
X ∨ Y ∧ ¬Z = 1 ∨ 0 ∧ ¬1 = 1+0.0 = 1
X ∨ Y ∧ ¬Z = 0 ∨ 1 ∧ ¬0 = 0+1.1 = 1
პასუხი: 4
მოცემულია F გამოთქმის სიმართლის ცხრილის ფრაგმენტი.რომელი გამოთქმა შეესაბამება F-ს?
| ა | ბ | C | ფ |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
1) (A → ¬B) ∨ C 2) (¬A ∨ B) ∧ C 3) (A ∧ B) → C 4) (A ∨ B) → C
გადაწყვეტილება:
1) (A → ¬B) ∨ C = (1 → ¬0) ∨ 0 = (1 → 1) + 0 = 1 + 0 = 1 (არ ემთხვევა მე-2 ხაზს)
2) (¬A ∨ B) ∧ C = (¬1 ∨ 0) ∧ 1 = (0+0).1 = 0 (არ ემთხვევა მე-3 ხაზს)
3) (A ∧ B) → C = (1 ∧ 0) → 0 = 0 → 0 = 1 (არ ემთხვევა მე-2 ხაზს)
4) (A ∨ B) → C (შეესაბამება F)
(A ∨ B) → C = (0 ∨ 1) → 1 = 1
(A ∨ B) → C = (1 ∨ 0) → 0 = 0
(A ∨ B) → C = (1 ∨ 0) → 1 = 1
პასუხი: 4
მოცემულია ლოგიკური გამოხატულება, რომელიც დამოკიდებულია 6 ლოგიკურ ცვლადზე:
X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6
ცვლადი მნიშვნელობების რამდენი სხვადასხვა ნაკრები არსებობს, რომლებისთვისაც გამოთქმა მართალია?
1) 1 2) 2 3) 63 4) 64
გადაწყვეტილება:
მცდარი გამოხატულება მხოლოდ 1 შემთხვევაში: X1=0, X2=1, X3=0, X4=1, X5=0, X6=0
X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6 = 0 ∨ ¬1 ∨ 0 ∨ ¬1 ∨ 0 ∨ 0 = 0
სულ ვარიანტები 2 6 \u003d 64, რაც ნიშნავს სიმართლეს
პასუხი: 63
მოცემულია F გამოთქმის სიმართლის ცხრილის ფრაგმენტი.
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | ფ |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
რა გამოთქმა შეესაბამება F-ს?
1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7
4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7
გადაწყვეტილება:
1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 = 0 + 1 + … = 1 (არ ემთხვევა პირველ ხაზს)
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7 = 0 + 0 + 0 + 0 + 0 + 1 + 0 = 1 (არ ემთხვევა პირველ ხაზს)
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7 = 1.0. …= 0 (არ ემთხვევა მე-2 ხაზს)
4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 (შეესაბამება F)
x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 = 1.1.1.1.1.1.1 = 1
x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 = 0. … = 0
პასუხი: 4
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | ფ |
| 0 | 1 | 1 | ||||||
| 1 | 0 | 1 | 0 | |||||
| 1 | 0 | 1 |
რა გამოთქმა შეიძლება იყოს F?
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8
გადაწყვეტილება:
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8 = x1 . x2 . 0 . … = 0 (არ ემთხვევა პირველ ხაზზე)
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8 (შეესაბამება F)
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 = … ¬x7 ∧ ¬x8 = … ¬1 ∧ ¬x8 = … 0 ∧ 0 (1¬x8 არ შეესაბამება - ხაზი)
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8 = ¬x1 ∨ ¬x2 ∨ ¬x3 … = ¬1 ∨ ∨ ∨ ∨ ¬x2. მატჩები მე-2 ხაზზე)
პასუხი: 2
ჭეშმარიტების ცხრილის ფრაგმენტი F გამოსახულებისთვის მოცემულია:
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | ფ |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
მიუთითეთ ამ გამონათქვამის სრული ჭეშმარიტების ცხრილის სხვადასხვა მწკრივების მინიმალური შესაძლო რაოდენობა, რომლებშიც მნიშვნელობა x5 იგივეა, რაც F.
გადაწყვეტილება:
განსხვავებული მწკრივების მინიმალური შესაძლო რაოდენობა, სადაც x5 იგივეა, რაც F = 4
პასუხი: 4
ჭეშმარიტების ცხრილის ფრაგმენტი F გამოსახულებისთვის მოცემულია:
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | ფ |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
მიუთითეთ ამ გამონათქვამის სრული სიმართლის ცხრილის სხვადასხვა მწკრივების მაქსიმალური შესაძლო რაოდენობა, რომლებშიც x6 მნიშვნელობა არ ემთხვევა F.
გადაწყვეტილება:
მაქსიმალური შესაძლო რიცხვი = 2 8 = 256
მწკრივების მაქსიმალური შესაძლო რაოდენობა, სადაც x6 არ ემთხვევა F = 256 - 5 = 251
პასუხი: 251
ჭეშმარიტების ცხრილის ფრაგმენტი F გამოსახულებისთვის მოცემულია:
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | ფ |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
მიუთითეთ ამ გამოხატვის სრული სიმართლის ცხრილის სხვადასხვა მწკრივების მაქსიმალური შესაძლო რაოდენობა, რომლებშიც მნიშვნელობა ¬x5 ∨ x1 იგივეა, რაც F.
გადაწყვეტილება:
1+0=1 - არ ემთხვევა F
0+0=0 - არ ემთხვევა F
0+0=0 - არ ემთხვევა F
0+1=1 - იგივე F
1+0=1 - იგივე F
2 7 = 128 – 3 = 125
პასუხი: 125
თითოეული ლოგიკური გამოხატულება A და B დამოკიდებულია 6 ცვლადის ერთსა და იმავე ნაკრებზე. ჭეშმარიტების ცხრილებში თითოეულ ამ გამონათქვამს აქვს ზუსტად 4 ერთეული მნიშვნელობების სვეტში. რამდენია ერთეულთა მინიმალური შესაძლო რაოდენობა A ∨ B გამოთქმის სიმართლის ცხრილის მნიშვნელობის სვეტში?
გადაწყვეტილება:
პასუხი: 4
თითოეული ლოგიკური გამოხატულება A და B დამოკიდებულია 7 ცვლადის ერთსა და იმავე ნაკრებზე. ჭეშმარიტების ცხრილებში თითოეულ ამ გამონათქვამს აქვს ზუსტად 4 ერთეული მნიშვნელობების სვეტში. რამდენია ერთეულთა მაქსიმალური შესაძლო რაოდენობა A ∨ B გამოთქმის სიმართლის ცხრილის მნიშვნელობის სვეტში?
გადაწყვეტილება:
პასუხი: 8
თითოეული ლოგიკური გამოხატულება A და B დამოკიდებულია 8 ცვლადის ერთსა და იმავე ნაკრებზე. ჭეშმარიტების ცხრილებში თითოეულ ამ გამონათქვამს აქვს ზუსტად 5 ერთეული მნიშვნელობების სვეტში. როგორია ნულების მინიმალური შესაძლო რაოდენობა A ∧ B გამოთქმის სიმართლის ცხრილის მნიშვნელობის სვეტში?
გადაწყვეტილება:
2 8 = 256 – 5 = 251
პასუხი: 251
თითოეული ლოგიკური გამოხატულება A და B დამოკიდებულია 8 ცვლადის ერთსა და იმავე ნაკრებზე. ჭეშმარიტების ცხრილებში თითოეულ ამ გამონათქვამს აქვს ზუსტად 6 ერთეული მნიშვნელობების სვეტში. როგორია ნულების მაქსიმალური შესაძლო რაოდენობა A ∧ B გამოთქმის სიმართლის ცხრილის მნიშვნელობის სვეტში?
გადაწყვეტილება:
პასუხი: 256
თითოეული ლოგიკური გამონათქვამი A და B დამოკიდებულია 5 ცვლადის ერთსა და იმავე ნაკრებზე. ორივე გამონათქვამის სიმართლის ცხრილებში შესატყვისი რიგები არ არის. რამდენ ერთეულს შეიცავს A ∧ B გამოთქმის სიმართლის ცხრილის მნიშვნელობის სვეტი?
გადაწყვეტილება:
ორივე გამონათქვამის სიმართლის ცხრილებში შესატყვისი რიგები არ არის.
პასუხი: 0
თითოეული ლოგიკური გამონათქვამი A და B დამოკიდებულია 6 ცვლადის ერთსა და იმავე ნაკრებზე. ორივე გამონათქვამის სიმართლის ცხრილებში შესატყვისი რიგები არ არის. რამდენ ერთეულს შეიცავს A ∨ B გამოთქმის სიმართლის ცხრილის მნიშვნელობის სვეტი?
გადაწყვეტილება:
პასუხი: 64
თითოეული ლოგიკური გამონათქვამი A და B დამოკიდებულია 7 ცვლადის ერთსა და იმავე ნაკრებზე. ორივე გამონათქვამის სიმართლის ცხრილებში შესატყვისი რიგები არ არის. რა არის ნულების მაქსიმალური შესაძლო რაოდენობა ¬A ∨ B გამოხატვის სიმართლის ცხრილის მნიშვნელობის სვეტში?
გადაწყვეტილება:
A=1,B=0 => ¬0 ∨ 0 = 0 + 0 = 0
პასუხი: 128
თითოეული ლოგიკური გამოხატულება F და G შეიცავს 7 ცვლადს. F და G გამონათქვამების ჭეშმარიტების ცხრილებში ზუსტად 8 იდენტური მწკრივია და მნიშვნელობის სვეტში ზუსტად 5 მათგანს აქვს 1. F ∨ G გამოხატვის სიმართლის ცხრილის რამდენი მწკრივი შეიცავს 1-ს მნიშვნელობის სვეტში?
გადაწყვეტილება:
არის ზუსტად 8 იდენტური მწკრივი და ზუსტად 5 მათგანს აქვს 1 მნიშვნელობის სვეტში.
ეს ნიშნავს, რომ ზუსტად 3 მათგანს აქვს 0 მნიშვნელობის სვეტში.
პასუხი: 125
ლოგიკური ფუნქცია F მოცემულია (a ∧ ¬c) ∨ (¬b ∧ ¬c). დაადგინეთ F ფუნქციის სიმართლის ცხრილის რომელი სვეტი შეესაბამება a, b, c ცვლადებიდან თითოეულს.
| ? | ? | ? | ფ |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
თქვენს პასუხში ჩაწერეთ ასოები a, b, c იმ თანმიმდევრობით, რომლითაც გამოჩნდება შესაბამისი სვეტები.
გადაწყვეტილება:
(a .¬c) + (¬b . ¬c)
როდესაც c არის 1, F არის ნული, ამიტომ ბოლო სვეტი არის c.
პირველი და მეორე სვეტების დასადგენად, შეგვიძლია გამოვიყენოთ მნიშვნელობები მე-3 რიგიდან.
(a . 1) + (¬b . 1) = 0
პასუხი: აბკ
ლოგიკური ფუნქცია F მოცემულია (a ∧ c)∨ (¬a ∧ (b ∨ ¬c)). დაადგინეთ F ფუნქციის სიმართლის ცხრილის რომელი სვეტი შეესაბამება a, b, c ცვლადებიდან თითოეულს.
იქიდან გამომდინარე, რომ a=0 და c=0, შემდეგ F=0 და მეორე რიგის მონაცემებით, შეგვიძლია დავასკვნათ, რომ მესამე სვეტი შეიცავს ბ.
პასუხი: კაბინა
ლოგიკური ფუნქცია F მოცემულია x ∧-ით (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z). სურათზე ნაჩვენებია F ფუნქციის სიმართლის ცხრილის ფრაგმენტი, რომელიც შეიცავს არგუმენტების ყველა კომპლექტს, რომლისთვისაც ფუნქცია F არის ჭეშმარიტი. დაადგინეთ F ფუნქციის სიმართლის ცხრილის რომელი სვეტი შეესაბამება x, y, z, w თითოეულ ცვლადს.
| ? | ? | ? | ? | ფ |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
თქვენს პასუხში ჩაწერეთ ასოები x, y, z, w იმ თანმიმდევრობით, რომლითაც გამოჩნდება შესაბამისი სვეტები.
გადაწყვეტილება:
x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z)
x . (¬y . z . ¬w . y ¬z)
იქიდან გამომდინარე, რომ x=0, შემდეგ F=0, შეგვიძლია დავასკვნათ, რომ მეორე სვეტი შეიცავს x.
პასუხი: wxzy
ჯერ განვსაზღვროთ რა გვაქვს ამოცანაში:
- ლოგიკური ფუნქცია F, რომელიც მოცემულია ზოგიერთი გამოსახულებით. ამ ფუნქციის სიმართლის ცხრილის ელემენტებიც ცხრილის სახით არის წარმოდგენილი ამოცანაში. ამრიგად, ცხრილიდან გამოსახულებაში კონკრეტული x, y, z მნიშვნელობების ჩანაცვლებისას, შედეგი უნდა ემთხვეოდეს ცხრილში მოცემულს (იხ. ახსნა ქვემოთ).
- ცვლადები x, y, z და სამი სვეტი, რომელიც შეესაბამება მათ. ამავდროულად, ამ პრობლემაში ჩვენ არ ვიცით რომელი სვეტი რომელ ცვლადს შეესაბამება. ანუ სვეტში Variable. 1 შეიძლება იყოს x ან y ან z.
- ჩვენ გვთხოვენ უბრალოდ განვსაზღვროთ რომელი სვეტი რომელ ცვლადს შეესაბამება.
განვიხილოთ მაგალითი.
გადაწყვეტილება
- ახლა კი გადაწყვეტილებას დავუბრუნდეთ. მოდით უფრო დეტალურად განვიხილოთ ფორმულა: \((\neg z) \სოლი x \vee x\სოლი y\)
- მას აქვს ორი კონსტრუქცია შეერთებით, რომლებიც დაკავშირებულია დისიუნქციით. მოგეხსენებათ, ყველაზე ხშირად დისიუნქცია მართალია (ამისთვის საკმარისია ერთ-ერთი ტერმინი იყოს ჭეშმარიტი).
- მოდით, ყურადღებით განვიხილოთ ხაზები, სადაც გამოთქმა F არის მცდარი.
- პირველი ხაზი ჩვენთვის არ არის საინტერესო, რადგან ის არ განსაზღვრავს სად არის (ყველა მნიშვნელობა ერთი და იგივეა).
- განვიხილოთ შემდეგ ბოლო ხაზი, მას აქვს ყველაზე მეტი 1, მაგრამ შედეგი არის 0.
- შეიძლება Z იყოს მესამე სვეტში? არა, რადგან ამ შემთხვევაში ფორმულაში ყველგან იქნება 1 და, შესაბამისად, შედეგი იქნება 1-ის ტოლი, მაგრამ სიმართლის ცხრილის მიხედვით, F-ის მნიშვნელობა ამ მწკრივში არის 0. შესაბამისად, z არ შეიძლება იყოს ცვლადი. . 3.
- ანალოგიურად, წინა ხაზისთვის, ჩვენ გვაქვს, რომ z არ შეიძლება იყოს ცვლადი. 2.
- აქედან გამომდინარე, z არის ცვლადი. ერთი.
- იმის ცოდნა, რომ z პირველ სვეტშია, განიხილეთ მესამე მწკრივი. შეიძლება x იყოს მეორე სვეტში? შეცვალეთ მნიშვნელობები:
\((\neg z) \სოლი x \vee x\სოლი y = \\ = (\neg 0) \სოლი 1 \vee 1\სოლი 0 = \\ = 1 \სოლი 1 \vee 0 = \\ = 1 \vee 0 = 1\) - თუმცა, სიმართლის ცხრილის მიხედვით, შედეგი უნდა იყოს 0.
- აქედან გამომდინარე, x არ შეიძლება იყოს var. 2.
- აქედან გამომდინარე, x არის ცვლადი. 3.
- ამიტომ, ელიმინაციის მეთოდის მიხედვით, y არის ცვლადი. 2.
- ასე რომ, პასუხი არის: zyx (z - ცვლადი 1, y - ცვლადი 2, x - ცვლადი 3).
სამუშაო დირექტორია.
სავალდებულო ეტაპის მქონე პროგრამების რაოდენობა
გაიარეთ ტესტი ამ ამოცანებისთვის
სამუშაოების კატალოგზე დაბრუნება
ვერსია MS Word-ში დასაბეჭდად და კოპირებისთვის
Executor A16 გარდაქმნის ეკრანზე დაწერილ რიცხვს.
შემსრულებელს ჰყავს სამი გუნდი, რომლებსაც ენიჭებათ ნომრები:
1. დაამატეთ 1
2. დაამატეთ 2
3. გავამრავლოთ 2-ზე
პირველი მათგანი რიცხვს ეკრანზე 1-ით ზრდის, მეორე 2-ით, მესამე ამრავლებს 2-ით.
პროგრამა A16 შემსრულებლისთვის არის ბრძანებების თანმიმდევრობა.
რამდენი პროგრამაა, რომელიც გადააქცევს თავდაპირველ რიცხვ 3-ს 12-ად და ამავე დროს პროგრამის გამოთვლების ტრაექტორია შეიცავს რიცხვს 10?
პროგრამის გამოთვლების ტრაექტორია არის ყველა პროგრამის ბრძანების შესრულების შედეგების თანმიმდევრობა. მაგალითად, პროგრამისთვის 132, საწყისი ნომრით 7, ტრაექტორია შედგება 8, 16, 18 რიცხვებისგან.
გადაწყვეტილება.
პროგრამების სასურველი რაოდენობა უდრის იმ პროგრამების რაოდენობის ნამრავლს, რომლებიც იღებენ 10 რიცხვს 3-დან იმ პროგრამების რაოდენობაზე, რომლებიც იღებენ 12-ს 10-დან.
მოდით R(n) იყოს პროგრამების რაოდენობა, რომლებიც გარდაქმნიან რიცხვ 3-ს n რიცხვად, ხოლო P(n) არის პროგრამების რაოდენობა, რომლებიც გარდაქმნიან რიცხვს 10-ს n რიცხვად.
ყველა n > 5-ისთვის, შემდეგი მიმართებები მართალია:
1. თუ n არ იყოფა 2-ზე, მაშინ R(n) = R(n - 1) + R(n - 2), ვინაიდან n-ის მიღების ორი გზა არსებობს - ერთის ან ორის მიმატებით. ანალოგიურად P(n) = P(n - 1) + P(n - 2)
2. თუ n იყოფა 2-ზე, მაშინ R(n) = R(n - 1) + R(n - 2) + R(n / 2). ანალოგიურად P(n) = P(n - 1) + P(n - 2) + P(n / 2)
თანმიმდევრულად გამოთვალეთ R(n) მნიშვნელობები:
R(5) = R(4) + R(3) = 1 + 1 = 2
R(6) = R(5) + R(4) + R(3) = 2 + 1 + 1 = 4
R(7) = R(6) + R(5) = 4 + 2 = 6
R(8) = R(7) + R(6) + R(4) = 6 + 4 + 1 = 11
R(9) = R(8) + R(7) = 11 + 6 = 17
R(10) = R(9) + R(8) + R(5) = 17 + 11 + 2 = 30
ახლა ჩვენ ვიანგარიშებთ P(n) მნიშვნელობებს:
P(11) = P(10) = 1
P(12) = P(11) + P(10) = 2
ამრიგად, პროგრამების რაოდენობა, რომლებიც აკმაყოფილებს პრობლემის პირობას, არის 30 2 = 60.
პასუხი: 60.
პასუხი: 60
წყარო: USE-2017-ის დემო ვერსია ინფორმატიკაში.
1. დაამატეთ 1
2. დაამატეთ 3
რამდენი პროგრამა არსებობს, რომლის საწყის რიცხვში 1, შედეგი არის რიცხვი 17 და გამოთვლის ტრაექტორია შეიცავს რიცხვს 9? პროგრამის გამოთვლების ტრაექტორია არის ყველა პროგრამის ბრძანების შესრულების შედეგების თანმიმდევრობა. მაგალითად, პროგრამისთვის 121, საწყისი ნომრით 7, ტრაექტორია შედგება 8, 11, 12 რიცხვებისგან.
გადაწყვეტილება.
ჩვენ ვიყენებთ დინამიური პროგრამირების მეთოდს. შექმენით მასივი dp, სადაც dp[i] არის i რიცხვის მიღების გზების რაოდენობა ასეთი ბრძანებების გამოყენებით.
დინამიური ბაზა:
გადასვლის ფორმულა:
dp[i]=dp + dp
ეს არ ითვალისწინებს 9-ზე მეტი რიცხვების მნიშვნელობებს, რომლებიც შეიძლება მიღებულ იქნას 9-ზე ნაკლები რიცხვებიდან (ამით გამოტოვეთ 9 ტრაექტორია):
პასუხი: 169.
პასუხი: 169
წყარო: სასწავლო სამუშაო ინფორმატიკაზე კლასი 11 ნოემბერი 29, 2016 ვარიანტი IN10203
არტისტი May17 აკონვერტებს რიცხვს ეკრანზე.
შემსრულებელს ჰყავს ორი გუნდი, რომლებსაც ენიჭებათ ნომრები:
1. დაამატეთ 1
2. დაამატეთ 3
პირველი ბრძანება ზრდის ეკრანის რიცხვს 1-ით, მეორე - 3-ით. პროგრამა May17 შემსრულებლისთვის არის ბრძანებების თანმიმდევრობა.
რამდენი პროგრამა არსებობს, რომლის საწყის რიცხვში 1, შედეგი არის რიცხვი 15 და გამოთვლის ტრაექტორია შეიცავს რიცხვს 8? პროგრამის გამოთვლების ტრაექტორია არის ყველა პროგრამის ბრძანების შესრულების შედეგების თანმიმდევრობა. მაგალითად, პროგრამისთვის 121, საწყისი ნომრით 7, ტრაექტორია შედგება 8, 11, 12 რიცხვებისგან.
გადაწყვეტილება.
ჩვენ ვიყენებთ დინამიური პროგრამირების მეთოდს. მოდით შევქმნათ მასივი dp, სადაც dp[i] არის i რიცხვის მიღების გზების რაოდენობა ასეთი ბრძანებების გამოყენებით.
დინამიური ბაზა:
გადასვლის ფორმულა:
dp[i]=dp + dp
მაგრამ ეს არ ითვალისწინებს ისეთ რიცხვებს, რომლებიც 8-ზე მეტია, მაგრამ ჩვენ შეგვიძლია მივიღოთ მათ 8-ზე ნაკლები მნიშვნელობიდან. შემდეგი, 1-დან 15-მდე dp-ის მნიშვნელობები იქნება მოცემული: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81 .
