Cycle Detection (Hamiltonian)

#include<stdio.h>
int a[20][20],x[20],n;
void next(int k)
{
 int j;
 while(1)
 {
 x[k]=(x[k]+1)%(n+1);
 if(x[k]==0)
 return;
 if((a[x[k-1]][x[k]])!=0)
 {
 for(j=1;j<=k-1;j++)
 if(x[k]==x[j])
 break;
 if(j==k)
 if((k<n)||(k==n&&a[x[n]][x[1]]!=0))
 return;
 }
 }
}
void hamilt(int k)
{
 int j;
 while(1)
 {
 next(k);
 if(x[k]==0)
 return;
 if(k==n)
 {
 printf(" ");
 for(j=1;j<=n;j++)
 printf("%2d",x[j]);
 }
 else
 hamilt(k+1);
 }
}
void main()
{
 int i,u,v;
 x[1]=1;
 printf("\n\n Enter how many nodes(0<n<20) :");
 scanf("%d",&n);
 printf("\n\n Enter your edges(ex- u sp v)(press 'e' for end) : \n");
 for(i=1;i<=(n*n)/2;i++)
 {
 if(getchar()=='e')
 break;
 scanf("%d%d",&u,&v);
 a[u][v]=a[v][u]=1;
 }
 hamilt(2);
 printf("\n\n");
}

Floyed Warshal

Input
5 7
1 2 4
1 3 1
1 5 6
2 5 3
2 4 1
3 2 1
4 5 1
0 0

#include<stdio.h>
#include<values.h>
#define N 100
#define INF MAXINT
int mat[N][N], path[N][N], n, e;
void initMat()
{
 for(int i=1; i<=n; i++)
 for(int j=1; j<=n; j++)
 mat[i][j] = INF;
}
void initPath()
{
 for(int i=1; i<=n; i++)
 for(int j=1; j<=n; j++)
 if(mat[i][j]!=INF)
 path[i][j] = j;
 else
 path[i][j] = 0;
}
void floyd_warshall()
{
 for(int k=1; k<=n; k++)
 for(int i=1; i<=n; i++)
 for(int j=1; j<=n; j++)
 if(mat[i][k]!=INF && mat[k][j]!=INF)
 if(mat[i][k]+mat[k][j] < mat[i][j])
 mat[i][j] = mat[i][k] + mat[k][j],
path[i][j] = path[i][k];
}
void showPath(int i, int j)
{
 if(i==j)
 {
 printf("->%d", i);
 return;
 }
 printf("->%d", i);
 showPath(path[i][j], j);
}
void main()
{
 while(scanf("%d%d", &n, &e) && n && e)
 {
 initMat();
 for(int i, j, c, k=0; k<e; k++)
 {
 scanf("%d%d%d", &i, &j, &c);
 mat[i][j] = c;
 }
 initPath();
 floyd_warshall();
 for(i=1; i<=n; i++)
 {
 for(j=1; j<=n; j++)
 if(path[i][j])
 {
 printf("%d", i);
 showPath(path[i][j], j);
 printf("\n");
 }
 printf("\n");
 }
 }
}

MinSum (DFS/QUEUE)

Input:

5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3

#include<stdio.h>
#include<conio.h>
#include<values.h>
#define N 100
#define MAX MAXINT
int mat[N][N], M[N][N], Q[N][4], front = -1, rear = -1;
int m, n, nc, nr, p, s, finalSum=MAX, leaf, r, c, i;
void init()
{
 for(int i=0; i<N; i++)
 for(int j=0; j<N; j++)
 M[i][j] = MAX, mat[i][j] = 0;
}
void nQ(int r, int c, int p, int s)
{ Q[++rear][0] = r; Q[rear][1] = c; Q[rear][2] = p;
 Q[rear][3] = s;}
void dQ(int *r, int *c, int *p, int *s)
{
 *r = Q[++front][0];
 *c = Q[front][1];
 *p = front;
 *s = Q[front][3];
}
void bfs()
{
 for(r=0, c=0; r<m; r++)
 nQ(r, c, -1, mat[r][c]);
 do
 {
 dQ(&r, &c, &p, &s);
 if(c<n-1)
 for(i=-1; i<2; i++)
 {
 nr=(m+r+i)%m, nc=c+1;
 if(M[nr][nc] > s+mat[nr][nc])
 nQ(nr, nc, p, s+mat[nr][nc]), M[nr][nc] = s+mat[nr][nc];
 }
 else if(s<finalSum)
 finalSum = s, leaf = p;
 } while(rear!=front);
}
void dfs(int leaf)
{
 if(Q[leaf][2]==-1)
 {
 printf(" <%d, %d>", Q[leaf][0]+1, Q[leaf][1]+1);
 return;
 }
 dfs(Q[leaf][2]);
 printf(" <%d, %d>", Q[leaf][0]+1, Q[leaf][1]+1);
}
void main()
{
 clrscr();
 int i, j, t;
 init();
 freopen("in.txt", "r", stdin);
 scanf("%d%d", &m, &n);
 for(i=0; i<m; i++)
 for(j=0; j<n; j++)
 {
 scanf("%d", &t);
 mat[i][j] = t;
 }
 bfs();
 printf("Final sum: %d\nPath:", finalSum);
 dfs(leaf);
}

BFS/DFS (Maze Problem)

Input :
8 8
#.#.#.#.
……..
#.#…..
#.##.#..
..#..##.
#..##…
…#…#
#.s#d.#.

#include<stdio.h>
#include<conio.h>
#include<values.h>
#define N 100
#define MAX MAXINT
int mat[N][N], Q[N][3], cost[N][N], front = -1, rear = -1;
int m, n, sc, sr, p, nr, nc, r, c, leaf, i, j, res[10][10];
int R[4] = {0, -1, 0, 1};
int C[4] = {-1, 0, 1, 0};
void nQ(int r, int c, int p)
{
 Q[++rear][0] = r, Q[rear][1] = c, Q[rear][2] = p;}
void dQ(int *r, int *c, int *p)
{
 *r = Q[++front][0], *c = Q[front][1], *p = front;
}
void bfs(int sr, int sc, int p)
{
 nQ(sr, sc, p);
 do{
 dQ(&r, &c, &p);
 for(int i=0; i<4; i++)
 {
 nr = r + R[i], nc = c + C[i];
 if(mat[nr][nc]==1)
 {
 if(cost[nr][nc]>cost[r][c]+1)
 cost[nr][nc]=cost[r][c]+1, nQ(nr, nc, p);
 }
 }
 } while (rear!=front);
 leaf = p;
}
void show()
{
 for(int i=0; i<=m; i++)
 {
 for(int j=0; j<=n; j++)
 {
 if(res[i][j])
 printf("X");
 else
 printf(" ");
 }
 printf("\n");
 }
}
void dfs(int leaf)
{
 if(Q[leaf][2]==-1)
 {
 res[Q[leaf][0]][Q[leaf][1]] = 1;
 return;
 }
 dfs(Q[leaf][2]);
 res[Q[leaf][0]][Q[leaf][1]] = 1;
}
void main()
{
 clrscr();
 char ch;
 freopen("maze.txt", "r", stdin);
 scanf("%d%d", &m, &n);
 getchar();
 for(i=0; i<m; i++)
 {
 for(j=0; j<n; j++)
 {
 cost[i][j] = MAX;
 scanf("%c", &ch);
 if(ch=='#')
 mat[i][j] = 0;
 else if(ch=='.')
 mat[i][j] = 1;
 else if(ch=='s')
 mat[i][j] = 2, sc = j, sr = i;
 else
 mat[i][j] = 3, res[i][j] = 1;
 }
 getchar();
 }
 bfs(sr, sc, -1);
 dfs(leaf); show();
 }

Fibnacci Number by Big Integer

#include<iostream.h>
#include<string.h>
int main()
{
 char *fibo[5001]={0};
 fibo[0]="0";
 fibo[1]="1";
 int l1=strlen(fibo[0]);
 int l2=strlen(fibo[1]);
 int l;
 for(long i=2;i<=5000;i++)
 {
 char str[10000];
 if(l1>=l2)l=l1;
 else l=l2;
 int ca=0;
 long j,k,m,p;
 for(j=l1-1,k=l2-1,m=0,p=0;p<l;j--,k--,m++,p++)
 {
 int s1;
 if(j<0)fibo[i-2][j]='0';
 s1=fibo[i-2][j]-48;
 int s2;
 if(k<0)fibo[i-1][k]='0';
 s2=fibo[i-1][k]-48;
 int ans=0;
 ans+=s1+s2+ca;
 if(ans>9)
 {
 str[m]=(ans-10)+48;
 ca=1;
 }
 else
 {
 str[m]=ans+48;
 ca=0;
 }
 }
 if(ca>0){str[m]=ca+48; m++;}
 str[m]='';
 fibo[i]=new char[m+1];
 long y=0;
 for(long x=m-1;x>=0;x--,y++)fibo[i][y]=str[x];
 fibo[i][y]='';
 l1=strlen(fibo[i-1]);
 l2=strlen(fibo[i]);
 }
 int n;
 while(cin>>n)
 {
 cout<<"The Fibonacci number for "<<n<<" is "<<fibo[n]<<"\n";
 }
 return 0;
}

Fibonacci Numbers O(log n)

 #include<stdio.h>
long conquer_fibonacci(long n){
long i,h,j,k,t;
i=h=1;
j=k=0;
while(n>0){
if(n%2==1){
t=j*h;
j=i*h + j*k +t;
i=i*k + t;
}
t=h*h;
h=2*k*h + t;
k=k*k + t;
n=(long) n/2;}
return j;}
int main(){
long n,res;
while(scanf("%ld",&n)==1){
res=conquer_fibonacci(n);
printf("%ld\n",res);}
return 0;
}

Big Number Square Root

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define MAX 1000
/****************************************************************/
int call_minus(char *large, char *small, char *result){
 char L[MAX], S[MAX];
 int l,s,now,hold,diff;
 l=strlen(large);
 s=strlen(small);
 if(l<s)
 return 0;
 if(l==s){
 if(strcmp(large, small)<0)
 return 0;
 }
 reverse(large,L);
 reverse(small,S);
 for(;s<l;s++)
 S[s]='0';
 S[s]='';
 for(now=0,hold=0;now<l;now++){
 diff=L[now]-(S[now]+hold);
 if(diff<0){
 hold=1;
 result[now]=10+diff+'0';
 }
 else{
 result[now]=diff+'0';
 hold=0;
 }
 }
 for(now=l-1;now>0;now--){
 if(result[now]!='0')
 break;
 }
 result[now+1]='';
 reverse(result,L);
strcpy(result,L);
 return 1;
}
/****************************************************************/
void call_sqrt(char *number,char *result,char *extra){
 int num,start,e,mul,l,r=0,len;
 char left[MAX],after[MAX];
 char who[5],temp[MAX],two[5];
 len=strlen(number);
 if(len%2==0){
 num=10*(number[0]-'0') + number[1]-'0';
 start=2;
 }
 else{
 num=number[0]-'0';
 start=1;
 }
 mul=(int) sqrt(num);
 result[0]=mul+'0';
 result[1]='';
 if(num-mul*mul ==0)
 extra[0]='';
 else
 sprintf(extra,"%d",num-mul*mul);
 for(;start<len;start+=2){
 e=strlen(extra);
 extra[e]=number[start];
 extra[e+1]=number[start+1];
 extra[e+2]='';
 two[0]='2';
 two[1]='';
 call_mult(result,two,left);
 l=strlen(left);
 for(mul=9;mul>=0;mul--){
 who[0]=mul+'0';
 who[1]='';
 strcat(left,who);
 call_mult(left,who,after);
 if(call_minus(extra,after,temp)==1){
 result[++r]=mul+'0';
 result[r+1]='';
 strcpy(extra,temp);
 break;
 }
else
 left[l]='';
 }
 }
 result[++r]='';
}
/******************************************************************/
int main(){
 char fir[MAX],ex[MAX],res[MAX];
 while(scanf("%s",&fir)==1){
 call_sqrt(fir,res,ex);
 int len=strlen(res);
 for(int i=0;i<len;i++) printf("%c",res[i]);
 printf("\n");
 }
 return 0;
}