Shunday qilib, variantlarni to'liq ro'yxatga olish imkoniyati cheklangan.
Keling, masalani hal qilishning boshqa usulini ko'rib chiqaylik. Kichikroq o'lchamdagi jadval uchun kichik masalani aniqlaymiz.
2
3
6
6
2
3
6
6
6
7
7
8
8
Natija quyidagicha
2
3
6
11
6
6
7
12
7
8
8
13
7
9
11
20
Masalani yechish algoritmi:
B[4×4] matritsasini kiritamiz.
Birinchi qator va birinchi ustun elementiga 0 ni belgilaymiz.
0
0
0
0
0
0
2
3
0
6
6
0
0
Dastur kodi: // “Toshbaqa” masalasi
//Mksimal yo’lni hisoblash masalasi
#include #include using namespace std;
Yechimning vaqt murakkabligi 0(n×m) ga teng. Har bir massiv B maksimal ikkita amalni (taqqoslash va qo'shish) talab qiladi.
300x300 massiv uchun operatsiyalarning umumiy soni 1000000 dan kam, ya'ni. million tezlikda ishlaydigan kompyuter vazifani bir soniyadan kamroq vaqt ichida bajarishi mumkin.
2-masala. sonlar ketma-ketligi berilsin.
Eng katta uzunlikdagi ortib boruvchi qatorni toping.
Kirish ma'lumotlari: 1, 5, 3, 7, 1, 4, 10, 15.
Chiqish ma'lumotlari: 1, 3, 4, 10, 15.
“Dag’al” kuch usuli.
1 (1) - 1 bitta kichik ketma-ketlik uchun.
1,2 (1; 2; 1, 2) - 3 uchun uchta kichik ketma-ketlik mavjud.
1,2,3 da (1; 2; 3; 1, 2; 1,3; 2,3; 1,2,3) - 7 ta kichik ketma-ketlik.
1,2,3,….,n uchun alohida pastki ketma-ketliklar soni ga teng.
Kichik vazifalarga ajratish
Fikr birinchi i elementlar orasidan eng katta ortib boruvchi ketma-ketlikni toping.
#include
using namespace std;
int main()
{
int a[8] = {1,5,3,7,1,4,10,15};
int n=8;
int p[8],d[8]={0};
int k=0;
int max;
for (int i=0; i{ max=0;
for (int j=0; j{if (a[j]max)) max=d[j];
}
d[i]=max+1;
}
for (int i=0; icout<for (int i=0; imax=d[1];
for (int i=0; icout<
}
3-masala. n butun soni berilgan. n sonni natural sonlar yig‘indisi sifatida ifodalash usullari sonini toping.
Kirish ma'lumotlari: butun son
Kirish ma'lumotlari: berilgan sonni natural sonlar yig'indisi sifatida ko'rsatish usullari soni.
#include
#include using namespace std;
int main()
{
int n=5;
int f[10][10]={0};
for (int i=0; i f[i][i]=1;
for (int k=0; k<=i-1; k++){
f[i][k]=0;
for (int j=0; j<=k; j++)
f[i][k]=f[i][k]+f[i-k][j];}
}
for (int i=0; i for (int j=0; jcout<<" "<}
Dastur natijasi
Demak, 5 sonini natural sonlar yig’indisi (1+2+2+1+1=7) yo’llar bilan ifodalash mumkin.
4-masala. n butun soni berilgan. Rekursiv formulalar yordamida n sonni natural sonlar yig‘indisi sifatida ifodalash usullari sonini toping.
Kirish ma'lumotlari: butun son
Kirish ma'lumotlari: berilgan sonni natural sonlar yig'indisi sifatida ko'rsatish usullari soni.
#include #include using namespace std;
int main()
{
int n=6;
int f[100][100]={0};
for (int i=0; i
for (int i=0; i for (int k=1; kfor (int k=i+1; k}
for (int i=0; i
cout<<" n= "<yechish uchun topshiriqlar
Topshiriq 1. N - raqamli omadli chiptalar sonini hisoblash talab qilinadi. Eslatib o'tamiz, agar chipta raqamlarining birinchi yarmining yig'indisi ikkinchi yarmining yig'indisiga teng bo'lsa, chipta omadli deb ataladi. Misol uchun, 064109 chiptasi omadli, chunki 0+6+4=1+0+9.
Ma'lumotlarni kiritish. INPUT.TXT kirish faylining bitta satrida N (N ≤ 100) juft natural son - chiptadagi raqamlar soni mavjud.
Chiqish. OUTPUT.TXT chiqish faylining yagona qatorida bitta butun sonni - N-raqamli omadli chiptalar sonini chiqarish kerak.
Misol
№
INPUT.TXT
OUTPUT.TXT
1
4
670
2
6
55252
3
12
39581170420
Topshiriq: N sonlar ketma-ketligi berilgan. Undan elementlarning minimal sonini olib tashlash kerak, shunda qolganlari qat'iy ortib boruvchi ketma-ketlikni hosil qiladi.
