6-Laboratoriya ishi Mavzu: Dinamik programmalash
Download 92.17 Kb.
|
6-tajriba. Algoritm loyihalash
Vaqt limiti: 1 sekund Xotira limiti: 64 MB Quyidagicha aniqlanadigan ketma-ketlik berilgan: F0=F1=F2=1, Fi=Fi-3+Fi-2+Fi-1(i>2). Bu ketma-ketlikning n-hadini topuvchi dastur tuzing. Bu son juda katta bo’lishimumkin, shuning uchun sizdan faqat uni 1000000007 (109+7) ga bo’lgandagi qoldiqnitopish so’raladi. Kiruvchi ma’lumotlar Birinchi qatorda n soni berilgan(0≤n≤106). Chiquvchi ma’lumotlar Bitta sonni – masalaning javobini chiqaring. Misollar
1-topshiriq Fibonatchi ketma-ketligi quyidagicha aniqlanadi. F0=F1=1, Fi=Fi-2+Fi-1(i > 1). Sizning vazifangiz n-fibonatchi sonini topuvchi dastur tuzish. Bu son juda katta bo’lishi mumkin, shuning uchun sizdan faqat uni 1000000007 (109+7) ga bo’lgandagi qoldiqni topish so’raladi. Kiruvchi ma’lumotlar: Birinchi qatorda bitta butun n soni berilgan. (0≤n≤1018). Chiquvchi ma’lumotlar: Birinchi qatorda bitta sonni−masalaning javobini chiqaring.
2-topshiriq Quyidagicha aniqlanadigan ketma-ketlik berilgan: F0=F1=F2=1, Fi=Fi-3+Fi-2+Fi-1(i>2). Bu ketma-ketlikning n-hadini topuvchi dastur tuzing. Bu son juda katta bo’lishimumkin, shuning uchun sizdan faqat uni 1000000007 (109+7) ga bo’lgandagi qoldiqnitopish so’raladi. Kiruvchi ma’lumotlar Birinchi qatorda n soni berilgan(0≤n≤1018). Chiquvchi ma’lumotlar Bitta sonni – masalaning javobini chiqaring. Misollar
3-topshiriq Quyidagicha aniqlanga ketma-ketlik berilagn. Ketma-ketlikning n-hadini toping. Javob yetarlicha katta bo’lishi mumkin. Shuning uchun sizdan faqat uni 109+7 ga bo’lgandagi qoldiqni topish so’raladi. Kiruvchi ma’lumotlar Birinchi qatorda n va k butun sonlari beriladi(0≤n≤106, 1≤k≤n). Chiquvchi ma’lumotlar F[n] ning qiymatini 109+7 ga bo’lgandagi qoldiqni chiqaring. Misollar
4-topshiriq Sizga bir o’lchamli sonli massiv berilgan. Massiv elementlari soni n. Sizningvazifangiz undan elementlari qiymatlari yi’gindisi eng katta bo’lgan qism massivnitopish. Qism massiv deb massivning biror (i..j)(i=1..n, j=i..n) uzluksiz indekslaridagielementlardan tuzilgan massivga aytiladi. Aynan shu maksimal yig’indini toping. Kiruvchi ma’lumotlar Birinchi qatorda bitta butun son n – massiv elementlari soni berilgan(1≤n≤105).Ikkinchi qatorda n ta butun son−massiv elementlari bitta probel bilan ajratib berilgan.Massiv elementlari modul jihatdan 106 dan oshmaydi. Chiquvchi ma’lumotlar Bitta sonni – masalaning javobini chiqaring. Misollar
Izoh: Birinchi misolda qism ketma-ketlik: 6 -5 1 4 5-topshiriq Quyidagicha aniqlanga ketma-ketlik berilagn. Ketma-ketlikning n-hadini toping. Javob yetarlicha katta bo’lishi mumkin. Shuning uchun sizdan faqat uni 109+7 ga bo’lgandagi qoldiqni topish so’raladi. Kiruvchi ma’lumotlar Birinchi qatorda n va k butun sonlari beriladi(0≤n≤1018, 1≤k≤50). Chiquvchi ma’lumotlar F[n] ning qiymatini 109+7 ga bo’lgandagi qoldiqni chiqaring. Misollar
6-topshiriq Sizga nxm matritsa berilgan. Matritsa sartlari 1 dan n gacha, ustunlari 1 dan m gachanomerlangan. Sizning vazifangiz undan elementlari qiymatlari yi’gindisi eng kattabo’lgan qism matritsani topish. Qism matritsa deb matritsaning 1≤x1≤x2≤n va1≤y1≤y2≤m indekslarni olsak shunday x1≤i≤x2 va y1≤j≤y2 shartni qanoatlantiruvchia[i][j] elementlarga aytiladi. Aynan shu maksimal yig’indini toping. Kiruvchi ma’lumotlar Birinchi qatorda ikkita butun son n va m sonlari berilgan(1≤n,m≤300). Keyingi nqatorda har birida m ta sondan matritsa elementlari bitta probel bilan ajratib berilgan.Matritsa elementlari butun va modul jihatdan 105 dan oshmaydi. Chiquvchi ma’lumotlar Bitta sonni – masalaning javobini chiqaring. Misollar
Izoh: Birinchi misolda qism matritsa: 6 -1 -4 9 0 10 7-topshiriq Edward works as an engineer for Non-trivial Elevators: Engineering, Research and Construction (NEERC). His new task is to design a brand new elevator for a skyscraper with h floors. Edward has an id´ee fixe: he thinks that four buttons are enough to control the movement of the elevator. His last proposal suggests the following four buttons: • Move a floors up. • Move b floors up. • Move c floors up. • Return to the first floor. Initially, the elevator is on the first floor. A passenger uses the first three buttons to reach the floor she needs. If a passenger tries to move a, b or c floors up and there is no such floor (she attempts to move higher than the h-th floor), the elevator doesn’t move. To prove his plan worthy, Edward wants to know how many floors are actually accessible from the first floor via his elevator. Help him calculate this number. Input The first line of the input file contains one integer h — the height of the skyscraper (1 ≤h ≤ 500 000). The second line contains three integers a, b and c — the parameters of the buttons (1 ≤ a,b, c ≤ 100 000). Output Output one integer number — the number of floors that are reachable from the first floor. Samples
8-topshiriq You are given a natural number N. Let’s consider sequences with N digits and containing only 0 and 1. It is well known that the number of such sequences equals to 2N. For example for N=3 such sequences: 000, 001, 010, 011, 100, 101, 110, 111. Your task is to calculate then number of sequences not containing three ones successively. Among given sequences 111 don’t satisfy to such requirement. Input The input contains single integer number N (1 ≤ N ≤ 70). Output Output one number – the answer to the problem. Samples
9-topshiriq
10-topshiriq
11-topshiriq Fizik olimlarimiz yaqinda yangi turdagi raqamli hisoblagichni yaratishdi. Bu hisoblagichning afzalligi shundaki, u ko’rsatkichning raqamlari yig’indisi M ga teng bo’lganda foydalanuvchiga hisobni to’lash haqida ma’lumot bildirib signal chaladi. Hisoblagich N xonali ko’rsatkichga ega. Lekin fizik olimlarimiz hisob-kitobga uncha usta emasligi uchun ularda qiziqarli bir muammo tug’ildi. Agar yangi hisoblagich ishlab boshlagandan keyin, bir marta to’liq aylanib yana yangi holga kelishida(yana 0 ni ko’rsatishi) necha marta signal chalishi qiziqarli savol albatta. Sizdan ushbu savolga javob berish so’raladi. Kiruvchi ma’lumotlar: ikkita butun son – N va M sonlari. (1 <= N <= 1000; 0 <= M <= 9000). E’tibor bering: hisoblagich ko’rsatgichi N xonali sonni ko’rsata oladi, ogohlantirish signali esa ko’rsatkich raqamlari yig’indisi M ga teng bo’lganda chalinadi. Chiquvchi ma’lumotlar: masala javobini 1000000007 (109+7) ga bo’lgandagi qoldiqni chiqaring.
Birinchi test uchun izoh: bu yerda javob 02,11,20. 12-topshiriq As we know, the Fibonacci numbers are defined as follows:: Given two numbers a and b, calculate . Input Input contains two non-negative integer numbers a and b (0 ≤ a ≤ b ≤ 109). Output Output S mod 1,000,000,000, since S may be quite large.
13-topshiriq Calculate the function: Input One positive integer n (1 ≤ n ≤ 1012). Output The value of f(n) modulo 1000000009. Samples
Download 92.17 Kb. Do'stlaringiz bilan baham: 
|