السلام عليكم و رحمه الله و بركاته اتمنى من احد ان يساعدني و جزاه الله الف خير فانى بحاجه ماسه للمساعده
ارجوا ان اجد الاجابه بهذا المنتدى الجميل
--------------------------------------------------------------------------
السوال
لدينا مصفوفه , كل خانه في هذه المصفوفه لها قيمه و المطلوب ايجاد طريق من اول المصفوفه إلى اخر عمد فيها بحيث يكون هذا الطريق ذو اقل مجموع قيم
و يحق لك فقط التحرك في هذه الاتجاهات
0 0 0
your here 0 0
0 0 0
هذا هو السوال بالغه الانجليزيه:
The Matrix Problem is the situation where you must travel from left to right through an N X N matrix such as the 6 X 6 matrix shown below:
Notice each cell in the matrix has an associated cost. You begin in the leftmost column and select a starting cell. You may not move up or down an element in the same column, you must always move to the next column towards the right; moving either diagonally or directly to the cell on the right. The goal of the problem is to minimize the cost traveling from left-most to the right-most column such that the sum of the cost of each cell along the path is at a minimum.
Dynamic Programming algorithm. The path followed by the dynamic programming solution is marked in red:
The total cost of the dynamic programming algorithm is 8.
هذا حلي لكن الناتج غلط فكيف يمكن ان اعدل عليه حتى احصل على الناتج الصح:
#include <iostream>
using namespace::std;
const int q1=4;
const int q2=4;
double Array[q1][q2]={16,5,4,6,2,5,1,9,8,7,6,5,4,3,2,1};//global variable
double Array2[q1][q2]={16,5,4,6,2,5,1,9,8,7,6,5,4,3,2,1};
//-------Class Object----------
class Object
{
public:
double cost;
int i,j;
};
//-------------------------------
//-----------fuction smallest , return the value of smallest element-------
double smalest(Object A,Object B,Object C)
{
double min;
min=A.cost;
Array2[A.i][A.j]=-1;
if(min>B.cost)
{ Array2[A.i][A.j]=Array[A.i][A.j];
min=B.cost;
Array2[b.i][b.j]=-1;
}
if(min>C.cost)
{ cout<<"in C loop "<<min<<"\n";
Array2[b.i][b.j]=Array[b.i][b.j];
Array2[A.i][A.j]=Array[A.i][A.j];
min=C.cost;
Array2[C.i][C.j]=-1;
}
return min;
}
//---------------------------------------------------------------------------
//------------------function shortest find the shortest path ---------------
Object shortest(int i,int j,int Jmax)
{
if(j>Jmax || i<0 ||i>=q1 )
{Object noValue;
noValue.cost=100000;
return noValue;
}
if(j==Jmax)
{Object temp;
temp.cost=Array[j];
temp.i=i;
temp.j=j;
return temp;
}
else
{
Object value;
value.cost= smalest(shortest(i,j+1,Jmax),shortest(i+1,j+1,Jmax),shortest(i-1,j+1,Jmax))+Array[j];
value.i=i;
value.j=j;
return value;}
}
//--------------------------------------------------------------------------------
int main()
{
Object cost;
cost =shortest(1,0,3);
cout<<cost.cost<<"\n";
for (int i=0;i<q1;i++)
{
for (int j=0;j<q2;j++)
cout<<Array2[j]<<" ";
cout<<"\n";
}
cout<<"\n";
for ( i=0;i<q1;i++)
{
for (int j=0;j<q2;j++)
cout<<Array[j]<<" ";
cout<<"\n";
}
return 0;}
------------------------------------------------------------------
اتمنى ان يساعدني احد ساكون ممتنه لكم جميعا فانا في ورطه
و اتمنى من الله ان يوفقنا جميعا