C++ Program help

[DeathHourbg]

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.

[lastchance]

Tell you what. You explain HOW you are going to do this and we'll help you with the code.

[DeathHourbg]

#include <iostream>
int main()
{
using namespace std;

int n;
cin >> n;

for (int i = 1; i <= n; i++)
{

}

return 0;
}

But I don't know how to write code about "which represent a strictly increasing sequence of digits"

[lastchance]

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).

[DeathHourbg]

This function if ( isStrictlyIncreasing( i ) ) cout << i << '\n'; should be inside the for loop right?
And bool isStrictlyIncreasing(int x) is like operator?

[lastchance]

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.

[DeathHourbg]

I have no idea how to declared and defined outside main ().

[lastchance]

Time to learn:
https://www.cplusplus.com/doc/tutorial/functions/

[jonnin]

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.

[Duthomhas]

@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:

0  --nope (“natural numbers” == “counting numbers”)
1
2
3
4
5
6
7
8
9
10 --nope
11 --nope (not _increasing_)
12
13
14
15
16
17
18
19
20 --nope
21 --nope
22 --nope
23
24
25
26
27
28
29
30 --nope
31 --nope
32 --nope
33 --nope
34
35
36
...
49

Here we see how it works — and gives us a clue how to construct such a sequence.

For joining digits into numbers, remember that numbers are just polynomials with powers of ten:

    5678  ==  5×10³ + 6×10² + 7×10¹ + 8×10⁰

Likewise,

    560  ==  56 * 10

Good luck!

[jonnin]

I would argue that I made it easier to code and more efficient at one stroke :P

[thmm]

The easiest seems to convert the number to a string and loop through all the digits.
A small demo to get you started:

#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
    return true;
}

int main()
{
    // natural numbers between 10 - 20
    
    for (int i = 10; i <= 20; ++i)
        if (is_natural_number(i))
            std::cout << i << "\n";
}

[lastchance]

Doesn't address the OP's question but there's only 511 (=2⁹-1) numbers to choose from. So @Jonnin's look-up table is not a bad idea.

This outputs all of them in ascending order.

#include <iostream>
#include <vector>
using namespace 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';
}

[Duthomhas]

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.

[jonnin]

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?

[lastchance]

511 is correct, @jonnin.

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.

[jonnin]

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).

[Duthomhas]

Heh, it’s a fun homework prompt. I did my version using a recursive function to compute the next integer.