Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: TSP and Minimum Weighted Route

Hi,
@Momerath and @Taywin... thanks for your replies. :)
I guess I wasn't clear enough about the question. I am not saying that triangular inequality should hold in TSP... that is a specialization of TSP - the metric TSP. All I'm saying (or rather asking) is that if my graph G(V,E) according to which the truck has to deliver goods is complete and it satisfies T.I. , then the problem of 'finding the route the truck must take so as to travel minimum distance' and TSP is one and the same.

Computer Science
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
TSP and Minimum Weighted Route

Hi,
Suppose there's a weighted undirected graph G(V,E) where each weight is the distance between two vertices. I have to visit all the vertices of the graph such that the total distance travelled is minimum.
Is this an instance of Traveling Salesman Problem?

Following is the amount of work that I've done on the problem so far.

Since the TSP states that each vertex has to be visited exactly once, for the problem stated to be an instance of TSP, G(V,E) must be a complete graph. Otherwise, it may not be possible to go to all the vertices without visiting some vertices more than once.
For example,

D-B-C
  |
  A

if we begin from A, we will have to go to B twice so as to reach all vertices.

The next thing that I figured out is that if G(V,E) satisfies triangular inequality, then the minimum weighted route will not visit each vertex more than once. Following is the proof that I came up with:-

Suppose, a portion of a complete graph is:-

D-B-C
  |
  A

Suppose, in the total minimum distance route , there is some edge A-B and and some edge B-D where vertex B is visited twice and is not the starting vertex.
So, there exists a path D-> ... ->u -> v -> ..... ->B where u and v are some vertices of graph.
So, one of the paths is A-> B -> D-> ...u...v...-> B. Let …

Computer Science
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: What is wrong with the follwoing javascript? (craftyjs used))

Nevr mind... found the solution. Thnaks anyways.

Web Development javascript
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
What is wrong with the follwoing javascript? (craftyjs used))

I am a newbie, in crafty as well as js, so pardon me if I might have made very silly errors in the following program.
What is wrong with the following code? The following code is supposed to create 5*5 matrix where each block would be a 60 pixel high and wide iceblock as stored in iceblock.jpg.

window.onload=function()
    {
        Crafty.init(500,500);
        Crafty.canvas();
        Crafty.sprite(60,"iceblock.jpg",{block : [0,0]});
        Crafty.c("iceblock",function(){
            init: function(){
                this.addComponent("2D, Canvas, Mouse, block");
                this.w = 60;
                this.h = 60;
            }
        });


    };
    for(var i=0;i<5;i++)
        {
            for(var j=0;j<5;j++)
            {
                Crafty.e("iceblock").attr({x: i*60,y: j*60})
            }
        }

The corresponding HTML code is:-

<!DOCTYPE html>
<head>
    <script type="text/javascript" src="crafty.js"></script>
    <script type="text/javascript" src="assignment.js"></script>
    <title>My Crafty Game</title>

</head>
<body>
</body>
</html>

When I open the HTML page, the complete output page is blank.
This is the link to the image.
http://postimage.org/image/ivqfhmjt9/

Web Development javascript
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Edit Distance Program- SIGSEGV

I made the table static and the program worked. Thanks for your help though.

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Edit Distance Program- SIGSEGV

PS:- I am unable to edit the original post.

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Edit Distance Program- SIGSEGV

@Ancient Dragon
I'm really sorry but I posted the wrong version of my code.
I was fiddling with the size of the table and posted the one with a.length aand b.length as dimensions.
In the actual code, the dimensions are indeed a.length()+1 and b.length()+1.
I am still getting seg fault. The problem is somewhere else. As I said I am getting correct answer for 1500 and 1000 length strings.
Sorry again for the inconvenience.

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Edit Distance Program- SIGSEGV

The following is my code for Edit Distance problem. The problem asks us to find the edit distance between two strings.
My code, I think gives the correct output. If I run the code with two strings of 1500 length each, I get the error. But if I run it when one is say 1500 and the other is 1000 characters long, the program works fine. I can't understand why I am getting seg fault. I don't think I'm accessing any unwanted area. Please help.

#include<stdio.h>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int main()
{
    int z,t;
    cin>>t;
    for(z=0;z<t;z++)
    {
        int i,j;
        string a,b;
        cin>>a;
        cin>>b;
        int table[a.length()][b.length()];
        for(i=0;i<=a.length();i++)
            table[i][0]=i;
        for(i=0;i<=b.length();i++)
            table[0][i]=i;
        for(i=1;i<=a.length();i++)
        {

            for(j=1;j<=b.length();j++)
            {
                int min=10000;
                if(table[i][j-1]+1 < min)
                    min=table[i][j-1]+1;
                if(table[i-1][j]+1<min)
                    min=table[i-1][j]+1;
                if(a[i-1]==b[j-1] && (table[i-1][j-1]<min))
                    min=table[i-1][j-1];
                else if(a[i-1]!=b[j-1]&&(table[i-1][j-1]+1<min))
                    min=table[i-1][j-1]+1;
                table[i][j]=min;
            }
        }
        /*for(i=0;i<=a.length();i++)
        {
            for(j=0;j<=b.length();j++)
                cout<<table[i][j]<<" ";
            cout<<endl;
        }*/
        printf("%d\n",table[a.length()][b.length()]);
    }
    return 0;
}
Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Binary Search Tree

@deceptikon

I'm not sure that I got what you meant there.
Let me rephrase my query.
Suppose I have a binary tree T.
I perform inorder traversal on the tree T.
Now, the output I get is sorted, say, 1 2 3 4 5 6 7.
Can I say, the binary tree T that gave this inorder traversal is a binary search tree.

Software Development c
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Binary Search Tree

While it is true that the inorder traversal of a binary search tree produces a sorted output, is the converse also true, i.e., if the inorder traversal of a binary tree is sorted, then is it necessarily a binary search tree?

Software Development c
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Assembler written in assembly language?

Thanks for the reply. :)

btw, when you say it "'must' have been written", are you too sure about it, or are you not too sure about it. If you are sure, could you possible give an example of the compiler/assembler written in machine language and another compiler/assembler which uses the machine language compiler/assembler to compile itself? (hope this does not sound too confusing :P)

Thanks.

Computer Science
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Can the following quicksort program be improved?

@deceptikon
I get your point (a little) about the swap process. But if the process is undefined, how does it actually manage to swap the elements in question (i can swap the elements successfully using this statement with gcc compiler).

I am not exactly sure as to what non-tail recursion means but I'll google that. Thanks for the tip. :)

Software Development c
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Can the following quicksort program be improved?

Well, the lines 23, 30 and 34 swap the two elements in question. The behaviour is not undefined. As a matter of fact the output of my quicksort program is correct. My only concern is the time that it takes.

Software Development c
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Assembler written in assembly language?

Firstly, I am not sure if this is the best place to ask the query. If no, please move it to the correct subforum.

Now, coming to my doubt, an assembler converts assembly language into opcodes, right? Now, to perform the conversion, assembler needs a certain algorithm. Whats the algorithm written in? Because if its written in a certain language, wouldnt we need assembler again to convert this algorithm to opcodes? Doesnt this lead to an infinite loop? Where does this process stop?

Computer Science
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Can the following quicksort program be improved?

Ok... i ran my quicksort program on my college lab's machine (i dunno its config) and it took 4 seconds on avg to sort 1 million elements. I ran it on my lappy (4 gb RAM, Intel Core i5-2410M Processor (2.3 GHz)) and it took 0.83 seconds to run the same number of elements. So, now I'm a little confused. I'd be really obliged if you could tell me if my quicksort program can be improved and if yes, then how.

Thanks in advance.

#include<stdio.h>

void quicksort(int*,int,int);

int n;

int main()
{
	scanf("%d",&n);
	int i, a[n];
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	quicksort(a,0,n-1);
	for(i=0;i<n;i++)
		printf("%d\n",a[i]);
}

void quicksort(int *a, int start, int end)
{
	if(start>=end)
		return;
	int pivot=(start+end)/2;//choosing mid element as pivot
	a[pivot]=a[end]+a[pivot]-(a[end]=a[pivot]);//swapping it ith last element
	pivot=end;
	int hi=start,i;//hi (high index) marks the beginning index of higher elements
	for(i=start;i<end;i++)
	{
		if(a[i]<=a[pivot])
		{
			a[hi]=a[i]+a[hi]-(a[i]=a[hi]);
			hi++;
		}
	}
	a[hi]=a[pivot]+a[hi]-(a[pivot]=a[hi]);
	pivot=hi;
	hi++;
	quicksort(a,start,pivot-1);
	quicksort(a,hi,end);
}
Software Development c
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Problem regarding data type conversion

@Adak...
Firstly, thanks for taking out the time to reply. :)

THat is the approach that I had tried at first. To find the number of digits after decimal point I wanted to check divisibility by .0001, .001, .01 and .1 . But I found out that % operator did not work with floating points. I couldn't use fmod() since I am not allowed to use any in built functions. ANyways, since the question said that the number of decimal points won't exceed 4, that's why I multiplied it by 10000.

Now, I don't think that the problem is with max limit or anything coz the program's not working for, lets say, 1.2972 but it is working for numbers "larger" than that as I have already specified in the original post.

Software Development c
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Problem regarding data type conversion

The following is the problem to which I am attempting a solution (in fact I have found the solution, there's a small doubt in a concept):-

Q4) Given a floating point number, write a program to convert it into its lowest irreducible
fractional form.
Note that the total number of digits before and after the decimal are less than 4, but greater than
0 (i.e there is at least one digit before the decimal and at least one digit after the decimal).
Sample Input:
3
2.4
2.5
3.2
Sample Output:
12/5
5/2
16/5

under the following constraints:-

General Instructions:
1) Every input starts with a number ‘n’, where ‘n’ are the total number of test cases that will be
followed, for eg. in Q1) n = 5, means that there are n test cases for this question, those are, 3,
60, 100, 1024, 23456.
2) Use of Arrays or any other advanced data structure isn’t allowed
3) Don’t use any pre-defined function in C library.

My first attempt for the solution was this:-

include<stdio.h>

int main()
{
    double p;
    int n,i,j,denominator=1;
    long int numerator;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%lf",&p);
        numerator=p*10000;
        denominator=10000;
        for(j=5000;j>0;j--)
        {
            if(numerator%j==0 && denominator%j==0)
            {
                numerator/=j;
                denominator/=j;
            }
        }
        printf("%ld/%d\n",numerator,denominator);
    }

    return 0;
}

This one produced disastrous results as the code had absolutely no regards for data types.
When I put the input as "3.4", it produced the …

Software Development c
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: 'error: iostream: no such file or directory' and other errors.

@sergent

lol..guess what..it worked. Apparently, codeblocks was saving it as a C file by default so thats why there were all these errors. Adding cpp at the end does the trick. Thanks ;)

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: 'error: iostream: no such file or directory' and other errors.

@firstperson
I don't think I'm running any project. I mean, I opened codeblocks and began working straight away.

@sergent
Its Windows XP SP2

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: 'error: iostream: no such file or directory' and other errors.

@firstperson

How am I creating my project? I am sorry but what's that question supposed to mean?

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
'error: iostream: no such file or directory' and other errors.

I am writing a c++ code (or any sort of code for that matter) after one complete year. And yet I don't think I could have become so bad that I can't make a Hello World program. Still, here I am with so many errors.

Here's the code:-

#include <iostream>

using namespace std;

int main()
{
    cout<<"Hello World!";
}

Here are the errors I am getting :-

C:\Documents and Settings\jay mata di\My Documents\c++\hello.c|1|error: iostream.h: No such file or directory|
C:\Documents and Settings\jay mata di\My Documents\c++\hello.c|3|error: expected '=', ',', ';', 'asm' or '__attribute__' before 'namespace'|
C:\Documents and Settings\jay mata di\My Documents\c++\hello.c||In function 'main':|
C:\Documents and Settings\jay mata di\My Documents\c++\hello.c|7|error: 'cout' undeclared (first use in this function)|
C:\Documents and Settings\jay mata di\My Documents\c++\hello.c|7|error: (Each undeclared identifier is reported only once|
C:\Documents and Settings\jay mata di\My Documents\c++\hello.c|7|error: for each function it appears in.)|
||=== Build finished: 5 errors, 0 warnings ===|

I guess the problem's with the compiler or my computer (I am using codeblocks.) I ran the program online. It ran just fine. How can I rectify it?

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
I am from India... trackers show my IP address is from USA

Recently.. I noticed that I can't access a few of my fb apps that were location specific. When I dug a little deeper, i found out that my computer was showing an IP Address that was from US. But I live in India.

I used the folowing two trackers:-

http://www.ipaddresslocation.org/ :- says my IP Address location is US.

http://www.find-ip-address.org/ :- CORRECTLY says that I belong from Indore, India.

Why these contradictions? I'd have said that the first site was bogus, only that facebook also seems to think that I'm from US. What's going on? Help please.

Networking
skilly commented: interesting +3
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
100 seeds and d/w speed 20 kbps!

Hey...guys while downloading one of the files I got a whopping 100 seeds.... and a sucking 20kbps download speed! I am very new to the world of torrents...in fact only began yesterday. So, I do not have much idea about torrents. I have a few questions. Firstly, the rate at which a file is downloaded, does it depend on the number of seeds AND my net speed or only on the number of seeds? I have the internet speed of 256kbps. So, is the 100 seeds and 20-25kbps d/w speed normal?

Well, i dared to make the assumption that it isn't. So, I looked for a few tweaks.... like port forwarding, multiple trackers etc. etc. But nothing seems to work. Please help.

Networking
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: How will I solve the following problems?Urgent!

Lol...Did I say I had no preparations?

As far as I know, I have been preparing for this competition for quite some time now. I have been studying graphs, trees, shortest paths, backtracking, dynamic programming etc.

I don't want you to post the answers for me. I just need you to guide me.

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
How will I solve the following problems?Urgent!

Hey guys, I have got a C++ competition tomorrow and it is very important for me. Following are few of the questions from past years. Please, please, pleeeasse read them and guide me on how do I solve them so that I get some preparation for tomorrow

http://pastebin.com/m226a46ab

http://pastebin.com/m79b943db.

http://pastebin.com/m370be9ea

http://pastebin.com/m1c2ede0c

PS:- OH man, I am so desperate!!

Please please help me.

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
The Knapsack Algorithm

Hi guys, can you please describe the knapsack algorithm in English. I googled this, the first page was wikipedia. The algorithm there is too mathematical which doesn't help me to understand the solution.

Can you please describe its algorithm?

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Kindly help me simplify the following graph class.

Ok...thanks. :)

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Boot disk failure

"Hasn't this guy herad of google?"The first thing that must've come into your mind when you read the title. But guess what, I did google. And this is a different sort of boot disk failure. It's not the Click of Death. So, then, what's it? I'll come to the point.


When I insert this CD, yes, one particular CD, into my computer, the computer hangs. When I restart the computer, it shows the error-> "Disk Boot Failure". When I remove this CD, the computer works fine. So, what's this connection between the CD and the hard disk. Personally, I've never heard of a case before where one particular CD was the hard disk's arch villian.

The thing is that the CD was working perfectly fine till yesterday. So, until and unless, the hard disk robbed the CD's house in the morning, I can't think of any reason to the wierd problem.

Kindly help me out guys.

Microsoft Windows windows-nt-2000-xp
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Kindly help me simplify the following graph class.

I have been studying graphs currently and came across a way to implement it.

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<functional>
#include<cstdlib>

using namespace std;

struct vertex;

struct edge
{
    vertex *dest;
    double cost;
    edge(vertex *a=NULL, double b=0)
    {
        dest=a;
        cost=b;
    }
};

struct vertex
{
    string name;
    vector<edge> adj;
    vertex(string s)
    {
        name=s;
    }
};

class graph
{
    public:
        typedef map<string, vertex *,less<string> > vmap;
        vmap work;
        void addvertex(const string&);
        void viewvertex();
        void addedge(const string& from, const string& to, double cost);
        void viewcostofedge(const string &from, const string &to);
};

void graph::addvertex(const string &name)
{
    vmap::iterator itr=work.begin();
    itr=work.find(name);
    if(itr==work.end())
    {
        vertex *v;
        v= new vertex(name);
        work[name]=v;
        return;
    }
        cout<<"\nVertex already exists!";

}

void graph::viewvertex()
{
    vmap::iterator itr=work.begin();
    for(;itr!=work.end();itr++)
    {
        cout<<"\n"<<itr->first;
    }
}


void graph::addedge(const string& from, const string& to, double cost)
{
    vertex *f=(work.find(from)->second);
    vertex *t=(work.find(to)->second);
    edge added(t,cost);
    f->adj.push_back(added);
}


void graph::viewcostofedge(const string &from, const string &to)
{
    vmap::iterator itr=work.find(from);
    vector<edge> v=(itr->second)->adj;
    vector<edge>::iterator itr1=v.begin();
    vertex *p;
    for(;itr1!=v.end();itr1++)
    {
        if(((*itr1).dest)->name==to)
            cout<<"\nThe cost is:-"<<(*itr1).cost;
    }
}

int main()
{
    int ch;

    graph g;
    string name;
    string string1,string2;
    double cost;
    do
    {
        cout<<"\n\n\n1.Add Vertex\n2.View Vertex\n3.Add Edge\n4.View Cost\n5.Exit\nEnter choice:-\n\n\n";
        cin>>ch;
        switch(ch)
        {
            case 1:
                cout<<"\nEnter the name of the vertex:-";
                cin>>name;
                g.addvertex(name);
                break;
            case 2:
                g.viewvertex();
                break;
            case 3:

                cout<<"\nEnter the spot:-";
                cin>>string1;
                cout<<"\nEnter the destination!";
                cin>>string2;
                cout<<"\nEnter cost:-";
                cin>>cost;
                g.addedge(string1,string2,cost);
                break;
            case 4:

                cout<<"\nEnter the spot:-";
                cin>>string1;
                cout<<"\nEnter the destination!";
                cin>>string2;
                g.viewcostofedge(string1,string2);
                break;
            case 5:
                exit(0);
            default:
                cout<<"\nWrong Choice!";
        }
    }while(1);
}

As you can see, the program seems overly complicated with all those …

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Suggest a good tutorial for graphs in c++

Maybe I'll elaborate more. I want to learn graphs so that I can solve algorithms such as shortest path.

OS-> Windows XP

Compiler-> Code::blocks

Software Development c++
Dave Sinkula commented: To you, this might be very much an illumination on your question. I read it as extremely vague, along the lines of, "I want to learn hammer so I can build apartment complex." -2
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: What is the best complier for C++ ?

I prefer code::blocks coz of the ease of use and the fact that well, coding in it looks so beautiful. It's just too nice. :)

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: new and delete operator

As far as I know delete does not return anything whereas new returns a pointer.

For example, when you write-->

new int;

A block of int is allocated in memory and a pointer is returned that points to the beginning of this block in the memory.

So, if you want to assign this pointer, you need to declare a pointer of type int that can hold this pointer.

int *x;
x= new int;
Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: I need help

Sorry but what is it that you want?

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: railway resevation system

Are you a 12th class student making a C++ project for CBSE boards?

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: expected primary expression error

There are quite a few errors in the program. Firstly, you don't mention the data type when you call a function.

So, in your function main:-

encrypt(string text, string message)

is incorrect.

It should be

encrypt(text, message)

And more importantly, you haven't declared text and message!

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Suggest a good tutorial for graphs in c++

Hi...

I'm trying to study graphs but I cant find a good tutorial on it. I googled it, but couldn't find what I needed.

Can you please suggest me a good tutorial on graphs in c++. I am basically looking for how a graph class is implemented in c++, an dthe functions to add vertexes.

Thanks in advance.
Edit/Delete Message

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: What's wroing with the following backtracking "Knight's Tour" program.

Hi...I just wanted to inform you that I corrected the program myself. Thanks for your replies.

Just in case you are interested, this is the corrected version of the program.

#include<iostream>

using namespace std;

int max_size=10;

class knight
{
    public:
        int count1;
        knight(int);
        int size;
        int arr[4][4];
        void mark(int ,int);
        void unmark(int , int);
        void print();
        void mf(int, int);
        bool unvisited(const int&);
};

knight::knight(int a)
{
    count1=1;
    int i,j;
    size=a;
    for(i=0;i<=a-1;i++)
        for(j=0;j<=a-1;j++)
            arr[i][j]=0;
}

void knight::mark(int x, int y)
{
    arr[x][y]=count1;
    count1++;
}

void knight::unmark(int x, int y)
{
    arr[x][y]=0;
    count1--;
}

void knight::print()
{
    for(int i=0;i<=size-1;i++)
        for(int j=0;j<=size-1;j++)
            cout<<"\nKnight went to the "<<i<<','<<j<<" block in "<<arr[i][j]<<"th turn!";
}

void knight::mf(int x, int y)
{
    if(count1==((size*size)))
        print();
    else if((x+2<=(size-1))&&(y+1<=(size-1))&&unvisited(arr[x+2][y+1]))
    {
        x+=2;
        y+=1;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
    else if((x+1<=(size-1))&&(y+2<=(size-1))&&unvisited(arr[x+1][y+2]))
    {
        x+=1;
        y+=2;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
    else if((x+2<=(size-1))&&(y-1>=0)&&unvisited(arr[x+2][y-1]))
    {
        x+=2;
        y-=1;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
    else if((x+1<=(size-1))&&(y-2>=0)&&unvisited(arr[x+1][y-2]))
    {
        x+=1;
        y-=2;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
    else if((x-2>=0)&&(y+1<=(size-1))&&unvisited(arr[x-2][y+1]))
    {
        x-=2;
        y+=1;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
    else if((x-1>=0)&&(y+2<=(size-1))&&unvisited(arr[x-1][y+2]))
    {
        x-=1;
        y+=2;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
    else if((x-2>=0)&&(y-1>=0)&&unvisited(arr[x-2][y-1]))
    {
        x-=2;
        y-=1;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
    else if((x-1>=0)&&(y-2>=0)&&unvisited(arr[x-1][y-2]))
    {
        x-=1;
        y-=2;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
}

bool knight::unvisited(const int& a)
{
    if(a==0)
        return 1;
    else return 0;
}


int main()
{
    knight example(4);
    example.mark(0,0);
    example.mf(0,0);
}
Software Development c++
Salem commented: Nice, can you now mark the thread "solved" +18
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: What's wroing with the following backtracking "Knight's Tour" program.

Thanks a lot for your quick response.:)

But I am don't think I understood your meaning. What do you mean when you say that I need to "output" those values?

Edit:-

Ah, I think I got you!

When I change the function ::mf() to this-->

void knight::mf(int x, int y)
{

    cout<<x<<endl<<y<<endl<<size<<endl<<count1<<endl<<endl;
    if(count1==((size*size)+1))
        print();
    else if(unvisited(arr[x][y])&&(x+2<=(size-1))&&(y+1<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x+2,y+1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x+1<=(size-1))&&(y+2<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x+1,y+2);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x+2<=(size-1))&&(y-1>=0))
    {
        mark(arr[x][y]);
        mf(x+2,y-1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x+1<=(size-1))&&(y-2>=0))
    {
        mark(arr[x][y]);
        mf(x+1,y-2);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-2>=0)&&(y+1<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x-2,y+1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-1>=0)&&(y+2<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x-1,y+2);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-2>=0)&&(y-1>=0))
    {
        mark(arr[x][y]);
        mf(x-2,y-1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-1>=0)&&(y-2>=0))
    {
        mark(arr[x][y]);
        mf(x-1,y-2);
        unmark(arr[x][y]);
    }
    cout<<"\nEnd of loop!\n";
}

I get this output-->

0
0
4
1

2
1
4
2

3
3
4
3

1
2
4
4

3
3
4
5

End of Loop!
End of Loop!
End of Loop!
End of Loop!
End of Loop!
Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
What's wroing with the following backtracking "Knight's Tour" program.

I have made a program to the follwoing problem:-

Another chessboard puzzle (this one reputedly solved by GAUSS at the age of four) is to find a sequence of moves by a knight that will visit every square of the board exactly once. Write a backtracking program that will input an initial position and search for a knight’s tour starting at the given position and going to every square once and no square more than once.

The program is:-

#include<iostream>

using namespace std;

int max_size=10;
int count1=1;
class knight
{
    public:
        knight(int);
        int size;
        int arr[10][10];
        void mark(int &);
        void unmark(int &);
        void print();
        void mf(int, int);
        bool unvisited(const int&);
};

knight::knight(int a)
{
    int i,j;
    size=a;
    for(i=0;i<=a-1;i++)
        for(j=0;j<=a-1;j++)
            arr[i][j]=0;
}

void knight::mark(int &a)
{
    a=count1;
    count1++;
}

void knight::unmark(int &a)
{
    a=0;
    count1--;
}

void knight::print()
{
    for(int i=0;i<=size-1;i++)
        for(int j=0;j<=size-1;j++)
            cout<<"\nKnight went to the "<<i<<','<<j<<" block in "<<arr[i][j]<<"th turn!";
}

void knight::mf(int x, int y)
{
    if(count1==((size*size)+1))
        print();
    else if(unvisited(arr[x][y])&&(x+2<=(size-1))&&(y+1<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x+2,y+1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x+1<=(size-1))&&(y+2<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x+1,y+2);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x+2<=(size-1))&&(y-1>=0))
    {
        mark(arr[x][y]);
        mf(x+2,y-1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x+1<=(size-1))&&(y-2>=0))
    {
        mark(arr[x][y]);
        mf(x+1,y-2);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-2>=0)&&(y+1<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x-2,y+1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-1>=0)&&(y+2<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x-1,y+2);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-2>=0)&&(y-1>=0))
    {
        mark(arr[x][y]);
        mf(x-2,y-1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-1>=0)&&(y-2>=0))
    {
        mark(arr[x][y]);
        mf(x-1,y-2);
        unmark(arr[x][y]);
    }
}

bool knight::unvisited(const int& a)
{
    if(a==0)
        return 1;
    else return 0;
}


int main()
{
    knight example(3);
    example.mf(0,0);
}

When, I run this program, nothing happens. Nothing is displayed.
Whats …

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Whats wrong with the following delete node in binary tree functions?

Oh...thanks...that worked! So, all my code was missing was was an "else"?

Whoa...I always considered else to be relatively unimportant! But its so freaking important!

Thanks again. :)

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Whats wrong with the following delete node in binary tree functions?

Hi guys...I am learning binary trees and its quite interesting. But I am unable to make4 a the delete a node function in it. Whenever I try to delete a node, a fatal error occurs and the program closes.

Can you please point the error out for me in the following program?

The program's a bit on the lengthier side as it also contains the insert a node function and inorder traversal function but it should be easy to trace the delete function.

Thanks for the help in advance.

#include<iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;

struct node
{
    int data;
    node *left;
    node *right;
};

class treetype
{
    node* root;
    public:
    treetype(){root=NULL;}
    bool finditem(const int &data);
    bool isempty();
    void insertitem(const int &data);
    void viewtree();
    void deletenode( int data);
};

bool find(node *,const int&);
void insert(node *&,const int&);
void view(node *tree);
void delete1(node *&,  int);
void delete2(node *&);
void getpredecessor(node *, int&);
bool treetype::isempty()
{
    if(root==NULL)
        return 1;
    else
        return 0;
}

bool treetype::finditem(const int &data)
{
    return find(root,data);
}

void treetype::insertitem(const int &data)
{
        insert(root,data);
}

void treetype::viewtree()
{
    view(root);
}

void treetype::deletenode(int data)
{
    delete1(root,data);
}

bool find(node *tree, const int &data)
{
    if(tree==NULL)
        return 0;
    else if(tree->data==data)
        return 1;
    else if(tree->data<data)
        return find(tree->right,data);
    else
        return find(tree->left,data);
}

void insert(node *&tree, const int &data)
{
    node *temp;
    temp= new node;
    temp->data=data;
    temp->right=temp->left=NULL;
    if(tree==NULL)
        tree=temp;
    else if(tree->data<data)
        insert(tree->right,data);
    else
        insert(tree->left,data);
}

void view(node *tree)
{
    if(tree!=NULL)
    {
        view(tree->left);
        cout<<endl<<tree->data;
        view(tree->right);
    }
}

void delete1(node *&tree,  int …
Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Sincere help required! Kindly help guys.

The previous links do not work.

Please download the files from here-->

http://rapidshare.com/files/327474804/inoi2009-qpaper.pdf
http://rapidshare.com/files/327473909/inoi2008-qpaper.pdf


Guys...Plleeeeeeeeeeaseeeee respond. I need your help badly.

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Sincere help required! Kindly help guys.

Each year IARCS organizes a series of competitive exams based on computing languages. I have great passion for computers and hence it is natural that I was attracted towards it.

Anyways, to cut the long story short, I was selected in ZCO 2010 and I have qualified for INOI 2010. If anyone wants more info on the competitions, check it out here-->
http://www.iarcs.org.in/inoi/current.php#zco2010

Of the 2 problems asked, I was able to solve one. Maybe, the other required the knowledge of trees which I didnt have. Anyways, I want to leave no stones unturned and get myself prepared nicely for the INOI and I'll be needing your help guys.

Following are two past year papers of INOI:-

http://www.iarcs.org.in/inoi/2008/inoi2008/inoi2008-qpaper.pdf
http://www.iarcs.org.in/inoi/2009/inoi2009/inoi2009-qpaper.pdf

Can you please, pleaseeeeeeeeee go through the question papers and give me the list of topics which I shall prepare?

Any help would be greatllyyyyyyyy appreciated. The exam would be on 24th Jan. So, I have approximately one month. I can study a lot during this time. Please, please help me.

Thanks in advance.

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Does the following compiler accept vectors?

Thanks. :)

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: chkdsk wont run

By the time I posted this quetsion..it was too late. I hadto get my computerformatted. Thanbks everyone r your replies though.

Microsoft Windows windows-nt-2000-xp
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
chkdsk wont run

Hey guys...I have delayed asking this for too long but maybe its high time.

My UPS faced some problems and it would automatically close down. So, basically windows was shut down improperly. Now, the problem is that my computer wont run chkdsk and thereare lots of damaged files.

I tried the chkdsk /f command and it said that it would run chkdsk on system restart but chkdsk won't run.

Now, how do I repair all those damaged files. Do you guys know how can I run chkdsk?

Microsoft Windows windows-nt-2000-xp
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Does the following compiler accept vectors?

Hi...kindly tell me if the following compiler accepts vectors.

C++ g++ (GCC) 4.1.2

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Kindly suggest me the algorithm

It is upto the user to enter any numbers.

The numbers I wrote are just an example.

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Kindly suggest me the algorithm

Note:- I am NOT asking you to write the program for me. I am NOT asking you to do the homework for me either. All I am asking you is if you could suggest an algorithm for me.


Present below are two algorithms. Can you please suggest me an algorithm to make the c++ program for them.Thanks in advance. :)

Problem 1 : Grid game

You are given a square grid of positive and negative numbers. You have to start at the top left corner of the grid and find a path to the bottom-right corner. In each step, you are only allowed to move one position to the right or one position down. As a special bonus, you are allowed at most one move that can be either to the left or up. Note that you are allowed to visit a position more than once as a result of this special move.

Your aim is to find such a path that has the maximum weight, where the weight of a path is the sum of all the numbers visited along the path.
Input format

The first line of the input contains one integer N, the number of rows and columns in the grid. Lines 2 to N+1 describe the N rows of the grid. Each of these N lines of input consists of N space separated integers, corresponding to the numbers in one row.
Notes

In all cases, N …

Software Development c++
Member Avatar for Nikhar
Nikhar 19 Junior Poster in Training
Re: Returning istream from a function

Thanks fbody. :)

Thanks fperson.:)

read(cin , student).clear()

This simple statement explained a lot.

Software Development c++