I have a task to write a program in C ++ with the following condition: To write a program for obtaining all natural numbers not exceeding a given n, which represent a strictly increasing sequence of digits. I will be very grateful if you help me with the code.
There are various ways of doing the problem. For your code, however, the simplest would be to write a function bool isStrictlyIncreasing( int x )
which returns true or false for a test number x.
Within your main() loop over i you could then just use if ( isStrictlyIncreasing( i ) ) cout << i << '\n';
So, it's that function isStrictlyIncreasing( int x ) that you need to write.
Note that you can peel off digits from the end of a number as x % 10 (followed by x /= 10 to move to the left). Each time you get a final digit compare it with the previous one (and return false if it fails). If you successfully reach x=0 without failing then you can return true.
Keep a variable stored as the previous digit to compare with (it can be initialised as something higher than a digit, e.g. 10).
This function if ( isStrictlyIncreasing( i ) ) cout << i << '\n'; should be inside the for loop right?
And bool isStrictlyIncreasing(int x) is like operator?
The function can be CALLED from inside the loop, but if it's a separate function then it needs to be declared and defined outside main().
Obviously, you could put its code inside the loop without a separate function, but I think you would benefit more from keeping it as a separate self-contained task and returning early from a function is often easier than breaking early out of a loop.
DeathHourbg wrote:
And bool isStrictlyIncreasing(int x) is like operator?
Not really, it's a simple function that returns either true or false depending on whether x has strictly increasing digits or not.
how big is N going to be? If this is a big N problem, you need to code the 'strictly increasing' efficiently. possibly a lookup table of the first 1000 integers (0-999) and then you can process upt to groups of 3 at a time instantly, eg 12345679 would check 679, 345, 12, logical and the 3 results, done in a jiffy. the largest value is 123456789 so anything larger than that you can stop iterating. 0 must be set to true; if single digits are not valid (unclear) then you can special case an actual 0 as input but it must be true in the table.
whole thing becomes
if( tbl[num%1000] && tbl[(num/1000)%1000] && tbl[(num/1000000)%1000])
its one you want
else
its not.
@jonnin, you are going totally overboard for a CS 101 homework assignment which OP has asked us to write for him.
[edit]
@Death-dude
A lot of your homework problems can be solved either naïvely, or by using some thinking.
The first question to ask yourself is something like “can I construct such a sequence without the computer?” Pick a small N, like 50:
#include <iostream>
#include <string>
bool is_natural_number(int num)
{
// if number < 10 return false
// convert num into a std::string, then loop from the second to the last digit. If a digit isn't
// greater than the previous one return false;
// at the end of the loop return true
returntrue;
}
int main()
{
// natural numbers between 10 - 20
for (int i = 10; i <= 20; ++i)
if (is_natural_number(i))
std::cout << i << "\n";
}
#include <iostream>
#include <vector>
usingnamespace std;
int main()
{
vector<int> valid;
for ( int i = 1; i <= 9; i++ ) valid.push_back( i );
int ibegin = 0, iend = valid.size();
for ( int numDigits = 2; numDigits <= 9; numDigits++ )
{
for ( int i = ibegin; i < iend; i++ )
{
for ( int d = valid[i] % 10 + 1; d <= 9; d++ ) valid.push_back( 10 * valid[i] + d );
}
ibegin = iend; iend = valid.size();
}
for ( int i : valid ) cout << i << '\n';
cout << "Number of valid integers: " << valid.size() << '\n';
}
Yes, but jonnin’s lookup table is a mature solution requiring more CS/algorithms knowledge than a first- or second-year student is expected to have.
At OP’s homework question level, the classwork is designed to get him thinking about how numbers and numeric operators work and apply simple flow control logic.
That is fair. This thing is going to take all day if you check every number one digit at a time, though. Ok, computers being what they are ... maybe just a few min, but still. And mine isnt the ultimate fast answer; I believe you can generate the numbers flat out but *that* would take some time to code up for a beginner for sure. And, the real answer .. get the 511 values into a table and everything else is false... :)
I didn't verify 511 ... did you count the little ones like 12 13 etc?
Every one of the digits 1...9 is either in or out, which gives 2^9 possibilities, but obviously the single case with none in isn't much use, so you have
2^9-1 or 511 possibilities. The code lists them.
Checking every number doesn't take as long as you think, either - there is a greater than 50% chance of returning false when you've only peeled off two digits. It took about a second with -O3 optimisation.
Hmm. Ill just admit that I don't see the 50% thing and look at it a bit more (don't tell me, it will be fun). You eliminated zero, a for all the numbers loop would have to look at it. 10234 10235 ... etc. A 'for the ones in the digit list' loop could avoid them. (see OP's for loop in his 2nd post).