contoh program backtracking "langkah catur kuda " C++

#include
#include
#include
const int DIM = 8 ;
const int MAX = DIM * DIM -1 ;
int v[DIM][DIM], row[MAX], col[MAX], rp,cp, index, MIN,p;
int A[DIM][DIM] =
{
{2,3,4,4,4,4,3,2},
{3,4,6,6,6,6,4,3},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{3,4,6,6,6,6,4,3},
{2,3,4,4,4,4,3,2}
};
int dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 },
dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 } ;
void direction()
{
int i ;
int C0_dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 }, // better for col 0
C0_dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 } ;
int C7_dx[] = { -2, -1, 1, 2, 2, 1, -1, -2 }, // better for col 7
C7_dy[] = { -1, -2,-2, -1, 1, 2, 2, 1 } ;
int R0_dx[] = { 1, 2, 2, 1, -1, -2, -2, -1 }, // better for row 0
R0_dy[] = { -2, -1, 1, 2, 2, 1, -1, -2 } ;
int R7_dx[] = { -2, -2, -1, 1, 2, 2, 1, -1 }, // better for row 7
R7_dy[] = { 1, -1, -2, -2, -1, 1, 2, 2 } ;
if ( cp < rp && cp < 4 )
for ( i = 0 ; i < 8 ; i++ )
{
dx[i] = C0_dx[i] ;
dy[i] = C0_dy[i] ;
}
if ( cp > rp && cp > 3 )
for ( i = 0 ; i < 8 ; i++ )
{
dx[i] = C7_dx[i] ;
dy[i] = C7_dy[i] ;
}
if ( rp < cp && rp < 4 )
for ( i = 0 ; i < 8 ; i++ )
{
dx[i] = R0_dx[i] ;
dy[i] = R0_dy[i] ;
}
if ( rp > cp && rp > 3 )
for ( i = 0 ; i < 8 ; i++ )
{
dx[i] = R7_dx[i] ;
dy[i] = R7_dy[i] ;
}
}
int valid( int a,int b ) {
if ( a < 0 || a >= DIM || b < 0 || b >= DIM )
return 0 ;
//if( a == rp && b == cp ) return 0 ;
return 1 ;
}
void Try(int r,int c,int pos ) {
int i,j,nr,nc ;
int *a ;
a = new int[8] ;
if( pos == MAX )
{
r = row[62] ;
c = col[62] ;
for ( i = 1 ; i < 8 ; i++ )
{
nr = r + dx[i] ;
nc = c + dy[i] ;
if ( valid( nr,nc ) && !v[nr][nc] )
break ;
}
if ( i == 8 ) return ;
r = nr ;
c = nc ;
for ( i = 0 ; i < 8 ; i++ )
{
nr = r + dx[i] ;
nc = c + dy[i] ;
if ( valid( nr,nc ) && nr == 5 && nc == 7 )
break ;
}
if ( i == 8 ) return ;
for ( i = 0 ; i < MAX ; i++ )
{ v[ row[i] ][ col[i] ] = i+1 ; }
for ( i = 0 ; i < 8 ; i++ )
{
for ( j = 0 ; j < 8 ; j++ )
{
if ( v[i][j] == 0 ) v[i][j] = 64 ;
printf("%-4d ",v[i][j] ) ;

}
printf("\n\n");
}
exit(0);
}
v[r][c] = pos + 1 ;
for ( i = 0 ; i < 8 ; i++ )
{
nr = r + dx[i] ;
nc = c + dy[i] ;
if( nr < 8 && nr >= 0 && nc < 8 && nc >= 0 && v[nr][nc] == 0 )
a[i] = --A[nr][nc] ;
else a[i] = 10 ;
}
for ( i = 0 ; i < 8 ; i++ )
{
MIN = 10 ;
for ( j = 0 ; j < 8 ; j++ )
{
if ( a[j] < MIN )
{
MIN = a[j] ;
p = j ;
}
}
a[p] = 10 ;
if ( MIN == 10 ) break ;
nr = r + dx[p] ;
nc = c + dy[p] ;
index++ ;
row[index] = nr ;
col[index] = nc ;
Try( nr,nc, pos+1 ) ;
index-- ;
v[nr][nc] = 0 ;
}
delete [] a ;
}
int main() {
int i,j ;
index = 0 ;
for ( i = 0 ; i < DIM ; i++ )
for ( j = 0 ; j < DIM ; j++ )
v[i][j] = 0 ;
/* printf("Enter Starting Row and Column : ");
scanf("%d%d",&rp,&cp ) ;
printf("\n");
rp-- ;
cp-- ; */
rp = 5 ;
cp = 7 ;
direction();
row[0] = rp ; col[0] = cp ;
v[rp][cp] = 1 ;
Try( rp,cp,0 ) ;
return 0 ;
getch();
}

Read more »

contoh program splitting C++

#include
#include
#include
#include

typedef struct { int nilai;
}rekarray;

rekarray rekA, rekB, rekC;

int main()
{
clrscr();
ifstream arrayC("array pusat.txt",ios::app);
ofstream arrayA("array B.txt",ios::app);
ofstream arrayB("array C.txt",ios::app);

if(arrayC.eof())
{
cout<<"file kosong";
}
else
{
do
{
if(rekA.nilai % 2 == 0)
{
arrayA.write((char*)&rekC,sizeof(rekC));
}
else
{
arrayB.write((char*)&rekC,sizeof(rekC));
}
arrayC.read((char*)&rekC,sizeof(rekC));
}while(arrayA.eof());
}

system("pause");
arrayA.close();
arrayB.close();
arrayC.close();
}

Read more »

contoh program rekursif C++

#include
#include

float TauGa(int A,int B)
{
if(B==0)
{
return 1;
}
else
{
return A*TauGa(A,B-1);
}
system("pause");
}

int main()
{ int A,B;
printf("masukan nilai yang akan dipangkatkan:");scanf("%d",&A);
printf("masukan pangkat:");scanf("%d",&B);
printf("%f",TauGa(A,B));
system("pause");
return 0;
}

Read more »

contoh program merging C++

#include
#include
#include

int main()
{
typedef struct {int nilai;
}Rekarray;

FILE *arrayA, *arrayB, *arrayC;
Rekarray rekA,rekB,rekC;

arrayA=fopen("arrayA.txt","rt");
fread(&rekA,sizeof(rekA),1,arrayA);
arrayB=fopen("arrayB.txt","rt");
fread(&rekB,sizeof(rekB),1,arrayB);
arrayC=fopen("array gabung.txt","wt");


while(!feof(arrayA) && feof(arrayB))
{
if(rekA.nilai <= rekB.nilai)
{
fwrite(&rekA,sizeof(rekA),1,arrayC);
fread(&rekA,sizeof(rekA),1,arrayA);
}
else
{
fwrite(&rekB,sizeof(rekB),1,arrayC);
fread(&rekB,sizeof(rekB),1,arrayB);
}
}

while (!feof(arrayA))
{
fwrite(&rekA,sizeof(rekA),1,arrayC);
fread(&rekA,sizeof(rekA),1,arrayA);
}

while (!feof(arrayB))
{
fwrite(&rekB,sizeof(rekB),1,arrayC);
fread(&rekB,sizeof(rekB),1,arrayB);
}

fcloseall();
system("pause");
return 0;
}

Read more »

binary tree

#include
#include
#include
#include
#include
#define MAXQUEUE 100

struct node
{
int data;
struct node *leftPtr;
struct node *rightPtr;
};
typedef node *NodeTree;
struct Queue
{
NodeTree data[MAXQUEUE];
int front;
int rear;
};
struct node *root;
int count=0;
int arrcount=0;
void initTree(int i);
void addTree(node *t,int i);
void getNo(node *t);
void viewTree(node *t,int x,int y);
void freeTree(node *t);
void insertNode(NodeTree *,int);
void breadth(NodeTree *,Queue *,int *);
void depth(NodeTree *,Queue *,int *);
void insertQueue(Queue *,NodeTree);
void insertQueue1(Queue *,NodeTree);
NodeTree * removeQueue(Queue *);

main()
{
int a,element,val;
NodeTree rootPtr=NULL;
start:
system("Cls");
printf("**********Binary Search Tree**********\n\n");
printf("\n Make your selection.");
printf("\n 1.Build a tree by inserting nodes.");
printf("\n 2.Search by Breadth First Search.");
printf("\n 3.Search by Depth First Search.");
printf("\n 4.View the tree.");
printf("\n 5.Chop down the tree.");
printf("\n 6.Exit.");
printf("\n\n**************************************");
cout<<"\nYour Choice?: ";
cin>>a;

if(a==1)
{
printf("Enter a node: ");
scanf("%d",&element);
insertNode(&rootPtr,element);
arrcount=0;
getNo(root);
if(arrcount==0){
initTree(element);
}
else {
addTree(root,element);
}
goto start;
}

else if(a==2)
{
Queue qPtr;
qPtr.front=0;
qPtr.rear=-1;
printf("Enter a value to search using Breadth First Search method: \n");
scanf("%d",&val);
if (val==0){
printf("Please enter a value more than zero.");
}
else {
breadth(&rootPtr,&qPtr,&val);
printf("\n");
}
getch();
goto start;
}

else if(a==3)
{
Queue qPtr;
qPtr.front=0;
qPtr.rear=-1;
printf("Enter a value to search using Depth First Search method: \n");
scanf("%d",&val);
if (val==0){
printf("Please enter a value more than zero.");
}
else {
depth(&rootPtr,&qPtr,&val);
printf("\n");
}
getch();
goto start;
}

else if(a==4)
{
system("Cls");
arrcount=0;
getNo(root);
if(arrcount==0){
printf("\nEmpty tree");
}
else{
viewTree(root,38,1);
}
getch();
goto start;
}

else if(a==5)
{
freeTree(root);root=NULL;
printf("\nThe Binary Tree has been chopped down.\n");
getch();
goto start;
}

else if(a==6)
{
printf("\n************** GoodBye! **************\n");
printf("");
exit(0);
}

else
{
printf("\nInvalid choice! Try again: ");
getch();
goto start;
}
return 0;
}

void initTree(int i)
{
root=(struct node *)malloc(sizeof(struct node));
root->data=i;
root->leftPtr=NULL;
root->rightPtr=NULL;
count++;
}
void addTree(struct node *t,int i)
{
struct node *p;
if((i>t->data)&&(t->rightPtr==NULL))
{
p=(struct node *)malloc(sizeof(struct node));
p->data=i;p->leftPtr=NULL;p->rightPtr=NULL;
t->rightPtr=p;
return;
}
if((idata)&&(t->leftPtr==NULL))
{
p=(struct node *)malloc(sizeof(struct node));
p->data=i;p->leftPtr=NULL;p->rightPtr=NULL;
t->leftPtr=p;
return;
}
if(i>t->data)addTree(t->rightPtr,i);
else if(idata)addTree(t->leftPtr,i);
}
void getNo(struct node *t)
{
if(t==NULL)return;
getNo(t->leftPtr);
arrcount++;
getNo(t->rightPtr);
}
void freeTree(struct node *t)
{
if(t!=NULL){
freeTree(t->leftPtr);
freeTree(t->rightPtr);
free(t);
}
}
void gotoxy(int x, int y)
{
COORD coord;
coord.X = x;
coord.Y = y;
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);
}
void viewTree(struct node *t,int x,int y)
{
if(t==NULL)
return;
else
{
gotoxy(x,y);
printf("%d",t->data);
viewTree(t->leftPtr,x-8,y+2);
viewTree(t->rightPtr,x+8,y+2);

}
}
void insertNode(NodeTree *treePtr,int element)
{
if(*treePtr==NULL)
{
*treePtr=NodeTree(malloc(sizeof(node)));

if(*treePtr!=NULL)
{
(*treePtr)->data=element;
(*treePtr)->leftPtr=NULL;
(*treePtr)->rightPtr=NULL;
}
else
printf("Insertion failed due to insufficient memory.\n");
}
else
{
if(element<(*treePtr)->data)
insertNode(&(*treePtr)->leftPtr,element);
else if(element>(*treePtr)->data)
insertNode(&(*treePtr)->rightPtr,element);
else
printf("Duplicate number found.\n");
}
}
void breadth(NodeTree *treePtr,Queue *qPtr, int *val)
{
if (*val==(*treePtr)->data){
printf("Found %d.",(*treePtr)->data);
*val=0;
return;
}
if((*treePtr)->leftPtr!=NULL)
insertQueue(qPtr,(*treePtr)->leftPtr);
if((*treePtr)->rightPtr!=NULL)
insertQueue(qPtr,(*treePtr)->rightPtr);
if(qPtr->rear>=qPtr->front)
breadth(removeQueue(qPtr),qPtr,&*val);
else {
printf("Data not found.");
}
}
void depth(NodeTree *treePtr,Queue *qPtr,int *val)
{
if (*val==(*treePtr)->data){
printf("Found %d.",(*treePtr)->data);
*val=0;
return;
}
if((*treePtr)->leftPtr!=NULL)
insertQueue(qPtr,(*treePtr)->leftPtr);
if((*treePtr)->rightPtr!=NULL)
insertQueue(qPtr,(*treePtr)->rightPtr);
if(qPtr->rear>=qPtr->front)
breadth(removeQueue(qPtr),qPtr,&*val);
else {
printf("Data not found.");
}
}
void insertQueue(Queue *qPtr,NodeTree tp)
{
qPtr->data[++qPtr->rear]=tp;
}
NodeTree * removeQueue(Queue *qPtr)
{
return &qPtr->data[qPtr->front++];
}

Read more »