Printable View
im a noob in c++ and i have a project to pass this weekend.. and i badly need help..
help me out please..
i need to:
find a 4-digit number that the difference between their digits arranged from greatest to smallest and smallest to greatest is the original number. (a<b<c<d) - (d<c<b<a) = original number.
please hep me out..
T____T
Fortunately, there are only 9000 4-digit numbers. That means you can easily solve this problem via brute force----simply search until you find a value which fits the criteria.
So all you need to do is:
1) Write a function to split out an integer into an array of its individual digits. This is pretty easy, there are hundreds of examples around the web.
2) Be able to sort the digits each way. This is again pretty easy if you leverage std::sort().
3) Write a function to combine the digits in the array into a single value again.
4) Subtract the two values so obtained and compare the difference to the original.
omg.. nosebleed terms..
im really a noob at using c++.. can you at least give me some codes or program lines in c++?
My father can do this better, as he claims he is an expert of C then C++. I will introcude this to him for a within-family run show caseQuote:
Originally Posted by vastolorde88
I advise a book by Barry Moose (?) Accelerated C++. a Cool informative book with various basic applications included
It's only Tuesday. You have plenty of time.Quote:
Originally Posted by vastolorde88
This board isn't here to do your homework for you.
The key is to tackle one small problem at a time, rather than trying to solve the whole thing at once. What's the very first thing you need to do which you don't understand?
Look up the "for" loop
"for" loop?!
Brute force means trying all possible combinations without a smart algorithm. So you try all numbers from 1000 to 9999 and check if any of these meets the required condition.
So you have to loop over all numbers from 1000 to 9999, that´s what you need the for loop for. That´s C++ fundamental.
Note that a 4-digit number xyzw can be constructed from the individual digits x, y, z and w with this formula: x*1000 + y*100 + z*10 + w. To utilize this to generate all numbers between 1000 and 9999 you use 4 nested loops, likeQuote:
Originally Posted by vastolorde88
Code:for (int x=1; x<10; ++x) {
for (int y=0; y<10; ++y) {
for (int z=0; z<10; ++z) {
for (int w=0; w<10; ++w) {
int n = x*1000 + y*100 + z*10 + w;
// n will take all numbers between 1000 and 9999
// and x, y, z, w are available to construct
// the other numbers required to determine
// whether n is a "hit".
}
}
}
}
First do this:
1. Take number from user, and display how many digits are in number. 715 has 3 digits.
2. Display all numbers separated by , (comma) - 7, 1, 5
3. Display the sum of all numbers - 13
4. Reverse the number, and display the difference (715-517) = 198
Now you are ready! ;)
With what?Quote:
Originally Posted by Ajay Vijay
There one solution and it's 6174 = 7641 - 1467.
Oh wow, that's going to be such a learning experience then.
Well, everybody should know that if they post homework here it may get stolen and made right in front of their eyes and there's nothing they can do about it! :)Quote:
Originally Posted by Lindley
I tried to solve it analytically on paper but only came as far as that the correct number(s) must appear in this list,
There were 21 numbers on the list so I checked them (skipping numbers with double digits because they're invalid). And there it was 6174.Code:for (int i=3; i<=8; ++i) {
for (int j=1; j<=i-2; ++j) {
int m = i*999 + j*90;
std::cout << m << "\n";
}
}
I've looked through this forum and it has become a "help-me-with-my-homework" life line these days. How did you find it, vastolorde88?
Weird! :confused:Quote:
Originally Posted by nuzzle
My post was relevant to the experience level of OP. He/She should know how to play with numbers, how to get the indivisual digits, and process them. Of course, the tasks I gave was not relevant to the original question in hand, the OP mentioned himself to be "noob in C++"
Well if "we" want to escape this, probably everyone have to ignore such topics asQuote:
Originally Posted by dc_2000
* i am noob
* please help, urgent
and so on, and so on. All these questions are not informative, and probably its homework.
This is the code for the ''brute force" solution. I'm not including the implementation of the MaxSorted() and MinSorted() functions because giving the whole thing out to you without any effort from your side would be quite uneducational.
Code:#include <stdio.h>
#include <conio.h>
int MaxSorted( int );
int MinSorted( int );
void Swap( int&, int& );
int main(int argc, char *argv[])
{
int i;
for( i=1000; i < 10000; i++ )
{
if( i == MaxSorted( i ) - MinSorted( i ) )
{
printf( "%d\n", i);
}
}
getch();
return 0;
}
To give you a hint, in these functions individual digits are extracted from the number and put into an array which is then sorted and then the return value is created using this array.
This is how you extract the individual numbers ( integer division and modulo operators are used ):
Code:
Arr[0] = Num % 10;
Arr[1] = ( Num % 100 ) / 10;
Arr[2] = ( Num % 1000 ) / 100;
Arr[3] = Num / 1000;
Next you must sort the array. I wrote bubble sort algorithm for this. But you can use anything you like. You may even find a sorting function in a library.
After sorting the array you create the MaxSorted numer:
Code:
return 1000*Arr[3] + 100*Arr[2] + 10*Arr[1] + Arr[0];
The MinSorted number is created by a minor change of the MaxSorted version. Just figure it out.
... and the result is really 6174. Programming is fun, just give it a try and do some research if you're not sure about something. I think I've given you enough hints,
regards
Koxin
It's hardly THE code for the brute force solution. It's one approach among several. I've suggested another one in #10 which avoids extracting the individual digits from the candidate numbers.Quote:
Originally Posted by Koxin
Besides your code has a logical bug. You need to test that all digits of a candidate number are unique. This follows from the a<b<c<d restriction.
Also there's no need to sort twice. One sort in either ascending or descending order is enougth. The other order is just the array read in reverse. A full general sort algoritm isn't necessary. 6 conditional swaps sorts a 4 member array (in the case the OP isn't allowed to use standard sort).
The code uses the "brute force" approach. It can be optimized and shortened. But who needs that? It yields the correct result anyway.
The way you expressed yourself suggests there's only one brute force solution namely the one supplied by you. This is not true, there are several.Quote:
Originally Posted by Koxin
And you claim I state the obvious just to have something to say?
I'd really like to understand the thought process for obtaining those 21 numbers.
CBV. It is very unlikely that nuzzle figured anything out on his own. This problem is related to what is called the Kaprekar Routine if you are curious.
Well I tried to find a solution with pen and paper but didn't get that far really. Anyway you have this relation,Quote:
Originally Posted by cbv
a < b < c < d
Where a, b, c and d are digits in any order in a number N. Now the problem is to find an N which equals this number M,
M = (d*1000 + c*100 + b*10 + a) - (a*1000 + b*100 + c*10 + d)
If you manipulate M algebraically you can get this,
M = (d-a)*999 + (c-b)*90
Now (d-a) and (c-b) are always positive because of a < b < c < d. That relation also says that b and c lies between a and d.
So (d-a) can vary between 8 (9-1) and 3 (because b and c lies between a and d). And with similar reasoning one can convince oneself that (c-b) can vary between 1 and (d-a)-2. In code that would be,
Code:for (int i=3; i<=8; ++i) { // variation of (d-a)
for (int j=1; j<=i-2; ++j) { // variation of (c-b)
int m = i*999 + j*90;
std::cout << m << "\n";
}
}
I had no idea that this was a known problem with a name. Then at least it's probably hard and I don't have to feel that bad I was unable to come up with a mathematical solution.Quote:
Originally Posted by souldog
Anyways I came as far as to this formulation,
Find a solution to
(d-a)*999 + (c-b)*90 = x*1000 + y*100 + z*10 + w
where a, b, c, d are digits with a<b<c<d,
and where x,y,z,w is a permutation of a,b,c,d.
Can you explain this part more: "(c-d) can vary between 1 and (d-a)-2"? Wouldn't c-d be negative?
You can also take the problem the other way round, and iterate over all a,b,c,d with a<b<c<d, and then verify then their diference is actually writable in an abcd form:
basically, you just need to check that aDiff is made of a,b,c and d.PHP Code:int main()
{
for(unsigned int a = 1; a<=6; ++a)
{
for(unsigned int b = a+1; b<=7; ++b)
{
for(unsigned int c = b+1; c<=8; ++c)
{
for(unsigned int d = c+1; d<=9; ++d)
{
int aBig = ((d*10+c)*10+b)*10+a;
int aSmall = ((a*10+b)*10+c)*10+d;
int aDiff = aBig - aSmall;
if (isMadeOf(aDiff, a,b,c,d))
{
std::cout << aDiff << " == " << aBig << " - " << aSmall << std::endl;
}
}
}
}
}
return 0;
}
One of the advantages here is that there are only 121 abcd numbers where a<b<c<d.
The other is that it requires no sort or nothing complicated.
Sorry it's a typo. I changed it my previous post.Quote:
Originally Posted by cbv
It should be "(c-b) can vary between 1 and (d-a)-2".