|
|
| səhifə | 2/2 | | tarix | 20.05.2022 | | ölçüsü | 50,37 Kb. | | #116065 |
| 8.2 labJadval o'lchami
|
Yo'l uzunligi
|
Yo'llar soni
|
Qo'shish operatsiyalari soni
|
Masalani hal qilish uchun taxminiy vaqt
|
|
6
|
20
|
100
|
0,00001 сек
|
|
14
|
3432
|
44616
|
0,045с
|
|
60
|
|
|
200 000 yil
|
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.
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;
int max(int a1, int b1)
{
if (a1>b1) return a1; else return b1;
}
int main()
{
setlocale(0,"");
int n=4;
const
int a[4][4]=
{
{ 2, 1, 3, 5 },
{ 4, 0, 1, 1 },
{ 1, 1, 0, 1 },
{ 0, 1, 2, 7 }
};
cout<<"Berilgan matritsa="<
for(int i=0; i
for(int j=0; jcout<cout<int b[5][5];
for(int i=0; i{
b[i][0]=0; b[0][i]=0;
}
for(int i=1; ifor(int j=1; jb[i][j]=max(b[i-1][j], b[i][j-1])+a[i-1][j-1];
cout<for(int i=0; ifor(int j=0; jcout<cout<}
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= "<
№
|
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. Dostları ilə paylaş: |
