#include #include using namespace std; /* 0 1 2 3 4 5 +-----+-----+-----+-----+-----+-----+ | 0 | 1 | 1 | 1 | 1 | 1 | 0 +-----+-----+-----+-----+-----+-----+ | 1 | 2 | 3 | 4 | 5 | 6 | 1 +-----+-----+-----+-----+-----+-----+ | 1 | 3 | 6 | 10 | 15 | 21 | 2 +-----+-----+-----+-----+-----+-----+ | 1 | 4 | 10 | 20 | 35 | 56 | 3 +-----+-----+-----+-----+-----+-----+ | 1 | 5 | 15 | 35 | 70 | 126 | 4 +-----+-----+-----+-----+-----+-----+ | 1 | 6 | 21 | 56 | 126 | 252 | 5 +-----+-----+-----+-----+-----+-----+ npath(0,0) = 0 npath(r,0) = 1 npath(0,c) = 1 npath(r,c) = npath(r,c-1) + npath(r-1,c) npath(2,2) = npath(2,1)+npath(1,2) = npath(2,0)+npath(1,1)+npath(1,1)+npath(0,2) = 1 + npath(1,0)+npath(0,1)+ npath(1,0)+npath(0,1)+1 = 1 + 1+1+1+1 + 1 = 6 npath(10,10)=npath(9,10) + npath(10,9) =npath(8,10)+npath(9,9) + npath(9,9)+npath(9,8) Print all of the possible paths. */ // recursion int npath( int r, int c ) { if ( r == 0 && c == 0 ) return 0; if ( r == 0 ) return 1; if ( c == 0 ) return 1; else return npath(r, c-1) + npath(r-1, c); } int cached[20][20] = { 0 }; int npath2( int r, int c ) { if ( r == 0 && c == 0 ) return 0; if ( r == 0 ) return 1; if ( c == 0 ) return 1; else { if ( cached[r][c] == 0 ) cached[r][c] = npath2(r, c-1) + npath2(r-1, c); return cached[r][c]; } } int npath3( int r, int c ) // bottom-up { int m[20][20] = { 0 }; m[0][0] = 0; for ( int i = 1; i <= r; i++ ) m[i][0] = 1; for ( int j = 1; j <= c; j++ ) m[0][j] = 1; for ( int i = 1; i <= r; i++ ) { for ( int j = 1; j <= c; j++ ) { m[i][j] = m[i-1][j] + m[i][j-1]; } } return m[r][c]; } int main() { clock_t start, end; int ans; start = clock(); ans = npath(15, 15); end = clock(); cout << ans << " (time: " << ((end-start) * 1. / CLOCKS_PER_SEC) << ")" << endl; start = clock(); ans = npath2(15, 15); end = clock(); cout << ans << " (time2: " << ((end-start) * 1. / CLOCKS_PER_SEC) << ")" << endl; start = clock(); ans = npath3(15, 15); end = clock(); cout << ans << " (time3: " << ((end-start) * 1. / CLOCKS_PER_SEC) << ")" << endl; return 0; }
Types of Loop
Loops are the elements of programming in which a part of code is repeated a particular number of times. Loop executes the series of statements many times till the conditional statement becomes false.
Loops
Any task which is repeated more than one time is called a loop. Basically, loops can be divided into three types as while, do-while and for loop. There are so many programming languages like C, C++, JAVA, PYTHON, and many more where looping statements can be used for repetitive execution.
While Loop
Loop is a feature in the programming language. It helps us to execute a set of instructions regularly. The block of code executes until some conditions provided within that Loop are true.
#include <iostream>
#include <ctime>
using namespace std;
/*
0 1 2 3 4 5
+-----+-----+-----+-----+-----+-----+
| 0 | 1 | 1 | 1 | 1 | 1 | 0
+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 5 | 6 | 1
+-----+-----+-----+-----+-----+-----+
| 1 | 3 | 6 | 10 | 15 | 21 | 2
+-----+-----+-----+-----+-----+-----+
| 1 | 4 | 10 | 20 | 35 | 56 | 3
+-----+-----+-----+-----+-----+-----+
| 1 | 5 | 15 | 35 | 70 | 126 | 4
+-----+-----+-----+-----+-----+-----+
| 1 | 6 | 21 | 56 | 126 | 252 | 5
+-----+-----+-----+-----+-----+-----+
npath(0,0) = 0
npath(r,0) = 1
npath(0,c) = 1
npath(r,c) = npath(r,c-1) + npath(r-1,c)
npath(2,2) = npath(2,1)+npath(1,2)
= npath(2,0)+npath(1,1)+npath(1,1)+npath(0,2)
= 1 + npath(1,0)+npath(0,1)+ npath(1,0)+npath(0,1)+1
= 1 + 1+1+1+1 + 1 = 6
npath(10,10)=npath(9,10) + npath(10,9)
=npath(8,10)+npath(9,9) + npath(9,9)+npath(9,8)
Print all of the possible paths.
*/
// recursion
int npath( int r, int c )
{
if ( r == 0 && c == 0 ) return 0;
if ( r == 0 ) return 1;
if ( c == 0 ) return 1;
else return npath(r, c-1) + npath(r-1, c);
}
int cached[20][20] = { 0 };
int npath2( int r, int c )
{
if ( r == 0 && c == 0 ) return 0;
if ( r == 0 ) return 1;
if ( c == 0 ) return 1;
else
{
if ( cached[r][c] == 0 ) cached[r][c] = npath2(r, c-1) + npath2(r-1, c);
return cached[r][c];
}
}
int npath3( int r, int c ) // bottom-up
{
int m[20][20] = { 0 };
m[0][0] = 0;
for ( int i = 1; i <= r; i++ ) m[i][0] = 1;
for ( int j = 1; j <= c; j++ ) m[0][j] = 1;
for ( int i = 1; i <= r; i++ )
{
for ( int j = 1; j <= c; j++ )
{
m[i][j] = m[i-1][j] + m[i][j-1];
}
}
return m[r][c];
}
int main()
{
clock_t start, end;
int ans;
start = clock();
ans = npath(15, 15);
end = clock();
cout << ans << " (time: " << ((end-start) * 1. / CLOCKS_PER_SEC) << ")" << endl;
start = clock();
ans = npath2(15, 15);
end = clock();
cout << ans << " (time2: " << ((end-start) * 1. / CLOCKS_PER_SEC) << ")" << endl;
start = clock();
ans = npath3(15, 15);
end = clock();
cout << ans << " (time3: " << ((end-start) * 1. / CLOCKS_PER_SEC) << ")" << endl;
return 0;
}
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 3 images
