Условие задачи    Алгоритм работы    Листинг программы    Набор тестов   

Условие задачи

Задана клетчатая доска n x n. Паук находится в верхнем правом углу. Он может двигаться на одну соседнюю клетку влево или вниз. Напишите программу, указывающую до каких клеток паук может добраться ровно Р разными путями.

      
Условие задачи    Алгоритм работы    Листинг программы    Набор тестов   

Алгоритм работы

Массив n x n заполняется единицами. Элемент в верхнем правом углу

(a[0][n-1]) заполняется нулём.

Начиная со второй строки и предпоследнего столбца массив заполняется по столбцам справа на лево и по строкам сверху вниз(исключается заполнение элементов первой строки и последнего столбца) элементами равными сумме вышестоящего элемента и элемента стоящего справа. В результате каждый элемент массива будет содержать число разных путей, которыми можно добраться до этого элемента из верхнего правого угла.

Далее, пробегая по созданному массиву, элементы сравниваются с заданным Р, в случае совпадения выводятся их координаты.

      
Условие задачи    Алгоритм работы    Листинг программы    Набор тестов   

Листинг программы

• Не рекурсивный вариант

  #include void mprint(int x, int y, int w, float q[100][100]); void main() { float a[100][100]; int i, j, n, p, f; cout<<"1) Matritsa NxN. N = "; cin>>n; for (i=0;i<n;i++) for (j=0;j<n;j++) a[i][j]=1; a[0][n-1]=0; for (i=1;i<n;i++) for (j=n-2;j>=0;j--) a[i][j]=a[i-1][j]+a[i][j+1]; mprint(n,n,4,a); cout<<"P = "; cin>>p; f=0; for (i=0;i<n;i++) for (j=0;j<n;j++) if (a[i][j]==p) {cout<<"a["<<(i+1)<<","<<(j+1)<<"] "; f++;}; if (f==0) cout<<"Elementov, do kotoryh mozhno dobratsya "<<p<<" raznymi putyami, NET\n"; } void mprint(int x, int y, int w, float q[100][100]) { int i, j; for (i=0;i<x;i++) { for (j=0;j<y;j++) { cout.width(w); cout<<q[i][j]<<" "; } cout<<endl; } }

• Рекурсивный вариант

  #include void mprint(int x, int y, int w, float q[100][100]); void mass1(int i, int n, float a[100][100]); void mass2(int i, int n, float a[100][100]); void mass3(int i, int n, int& f, int p, float a[100][100]); void main() { float a[100][100]; int i, j, n, p, f; cout<<"1) Matritsa NxN. N = "; cin>>n; mass2(0,n,a); a[0][n-1]=0; mass1(1,n,a); mprint(n,n,4,a); cout<<"P = "; cin>>p; f=0; mass3(0,n,f,p,a); if (f==0) cout<<"Elementov, do kotoryh mozhno dobratsya "<<p<<" raznymi putyami, NET\n"; } void mprint(int x, int y, int w, float q[100][100]) { int i, j; for (i=0;i<x;i++) { for (j=0;j<y;j++) { cout.width(w); cout<<q[i][j]<<" "; } cout<<endl; } } void mass1(int i, int n, float a[100][100]) { int j; for (j=n-2;j>=0;j--) a[i][j]=a[i-1][j]+a[i][j+1]; i++; if (i<n) mass1(i,n,a); } void mass2(int i, int n, float a[100][100]) { int j; for (j=0;j<n;j++) a[i][j]=1; i++; if (i<n) mass2(i,n,a); } void mass3(int i, int n, int& f, int p, float a[100][100]) { int j; for (j=0;j<n;j++) if (a[i][j]==p) {cout<<"a["<<(i+1)<<","<<(j+1)<<"] "; f++;}; i++; if (i<n) mass3(i,n,f,p,a); }

  
  

      
Условие задачи    Алгоритм работы    Листинг программы    Набор тестов   

Набор тестов к программе

1.

N = 5

 1     1     1     1     0
 5     4     3     2     1
15    10     6     3     1
35    20    10     4     1
70    35    15     5     1

P=4

A[2;2] A[4;4]

2.

N = 5

 1     1     1     1     0
 5     4     3     2     1
15    10     6     3     1
35    20    10     4     1
70    35    15     5     1

P=7

Elementov, do kotoryh mozhno dobratsya 7 raznymi putyami, NET

Автор решения: Шихов Антон

группа: 121Ми

год: 2008

Автор задачи: Гладков В.П. Курс лабораторных работ по программированию: Учебное пособие для специальностей электротехнического факультета ПГТУ/ Перм.гос.техн.ун-т.-Пермь,1998.-153с.