### How can I do this without a nested loop

Basically, write a program that inputs an integer n, and applies the following procedures until n=1: if n is even, divide by two, if n is odd, multiply n by 3 and add 1.

I wrote the program, but with a nested loop, however, I was not supposed to use one. How could I do it without it?

#include <iostream>
using namespace std;
int main(){
int n;
cin>>n;
if (n!=0) {
while (n!=1 && n%2==0){
n=n/2;
cout<<n<<endl;
while (n!=1 && n%2==1){
n=n*3+1;
cout<<n<<endl;
}
}
}
cout<<n<<endl;
}
To repeat a block of code you need either a loop or use goto.

Using goto:

 123456789101112131415161718192021222324 #include int main() { std::cout << "Enter a number: "; int n; std::cin >> n; loop: if (n != 1) { if (n % 2 == 0) { n = n / 2; std::cout << n << '\n'; } else { n = n * 3 + 1; std::cout << n << '\n'; } goto loop; } std::cout << '\n' << n << '\n'; }

Using goto is really sloppy.

Using a loop (while):

 1234567891011121314151617181920212223 #include int main() { std::cout << "Enter a number: "; int n; std::cin >> n; while (n != 1) { if (n % 2 == 0) { n = n / 2; std::cout << n << '\n'; } else { n = n * 3 + 1; std::cout << n << '\n'; } } std::cout << '\n' << n << '\n'; }

And PLEASE, learn to use code tags, it makes reading your code MUCH easier.
http://www.cplusplus.com/articles/jEywvCM9/
Last edited on
A third possibility is loop using recursion, but that can be a major headache.
 12345678910 #include using namespace std; int main() { unsigned long long n; cout << "Input n: "; cin >> n; for( ; n != 1; n = n % 2 ? n * 3 + 1 : n >> 1 ) cout << n << '\n'; cout << n; }

 Input n: 9 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Try it for n = 837799
Recursion, in this case, is not such an headache ;-)
Example (more or less copied from FurryGuy's and Lastchance's codes):
 123456789101112131415161718192021 #include void Collatz(unsigned val); int main() { std::cout << "Please enter a POSITIVE integer: "; int i; std::cin >> i; std::cout << '\n'; Collatz(i); } void Collatz(unsigned val) { std::cout << val << '\n'; if(1 != val) { if(val % 2) { Collatz(val * 3 + 1); } else { Collatz(val >> 1); } } }

Even when copying code, it is a good idea to stop and think for a second.

In particular, when we see a loop, think of the boundary conditions:
in this case, what would happen if n is initially zero (the user entered zero)?

Also, don't copy obfuscated code blindly: transparent code is good code.
for instance, val >> 1 does not optimize anything; people who write compilers would know at least as much about low level efficiency as the palooka who thinks that the code is being made more efficient by applying strength reduction at source code level.

For instance, in he best case scenario, foo and palooka_foo would generate the same machine code, as would bar, alt_bar, palooka_bar and palooka2_bar

 1234567891011 unsigned int foo( unsigned int n ) { return n/2 ; } unsigned int palooka_foo( unsigned int n ) { return n >> 1 ; } unsigned int bar( unsigned int n ) { return n*3 + 1 ; } unsigned int alt_bar( unsigned int n ) { return n+n+n + 1 ; } unsigned int palooka_bar( unsigned int n ) { return ( (n<<2) - n ) + 1 ; } unsigned int palooka2_bar( unsigned int n ) { return ( (n<<1) + n ) + 1 ; }

https://godbolt.org/g/ye8cmB

It is possible that the attempted 'clever' code may result in suboptimal machine code; as in the case of palooka_bar here; optimisers find it easier to optimise transparent code.
https://godbolt.org/g/fHibQu

While learning C++, it is important to cultivate good programming habits; basic programming hygiene.
The real problem with this sequence (hailstone sequence or Collatz conjecture) is that nobody has ever proved that the sequence is guaranteed to terminate for all n. However, there is, apparently, quite a substantial financial prize if you do!

Crikey, looks like someone above really did have a bad-hair day!
Last edited on
@afatperson:
You probably had some logical thought that did lead to this nested version of yours:
 12345678910 if (n!=0) { while ( n!=1 && n%2==0 ) { n=n/2; cout<

Care to share a bit of that logic?

Note:
* The sanity check on line 1 is good but not perfect. The user could give a negative number.

* If we reach line 3, then n is even and half of it is thus odd. Therefore, first time on line 5 always succeeds, unless n is already 1.

* On the other hand three times an odd value is odd too and the plus one makes it even. Therefore, the inner loop cannot iterate more than once.

* The outer loop never evaluates its body, if the n is not even. What values did you test your program with?
 Recursion, in this case, is not such an headache ;-)

 12345678910111213141516171819202122 #include unsigned long long GetFibNum(unsigned long long FibIndex) { if (FibIndex < 2) { return FibIndex; } else // recursion if FibIndex >= 2 { return GetFibNum(FibIndex - 1) + GetFibNum(FibIndex - 2); } } int main() { std::cout << "Enter 0-based index of desired Fibonacci Number: "; unsigned long long Index = 0; std::cin >> Index; std::cout << "Fibonacci number is: " << GetFibNum(Index) << '\n'; }

Run this for an index number greater than 50, say 100, and see how long it takes to get an answer.

Using iteration (just the function shown):
 1234567891011121314151617181920 unsigned long long GetFibNum(unsigned long long FibIndex) { unsigned long long minusTwo = 1; unsigned long long minusOne = 1; unsigned long long answer = 2; if (FibIndex < 3) { return 1; } for (FibIndex -= 3; FibIndex != 0; FibIndex--) { minusTwo = minusOne; minusOne = answer; answer = minusOne + minusTwo; } return answer; }

Both examples are easy to program, the number of function calls the recursive example has to make is annoying and a headache.
> the number of function calls the recursive example has to make is annoying and a headache.

If the same algorithm is implemented, with one version being recursive and the other being iterative,
the difference in performance between the two would not be significant.

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071 #include #include #include #include bool limits_check( unsigned long long a, unsigned long long b ) { return a <= ( std::numeric_limits::max() - b ) ; } // get the largest n that we can handle (with standard built in types) on this implementation std::size_t max_nfib_ull() { unsigned long long a = 0 ; unsigned long long b = 1 ; std::size_t cnt = 1 ; while( limits_check(a,b) ) { b = a + b ; a = b - a ; ++cnt ; } return cnt ; } unsigned long long fib_recursive( std::size_t n, unsigned long long a = 0, unsigned long long b = 1 ) { if( n == 0 ) return a ; else if( n == 1 ) return b ; else return fib_recursive( n-1, b, a+b ) ; } unsigned long long fib_iterative( std::size_t n ) { unsigned long long a = 0 ; unsigned long long b = 1 ; if( n == 0 ) return a ; else for( ; n > 1 ; --n ) { b = a + b ; a = b - a ; } return b ; } int main() { const std::size_t n = max_nfib_ull() ; { const auto start = std::clock() ; const auto result = fib_recursive(n) ; const auto end = std::clock() ; std::cout << "fib_recursive(" << n << ") == " << result << '\n' << (end-start) * 1000.0 / CLOCKS_PER_SEC << " milliseconds\n" ; assert( n>=93 && fib_recursive(93) == 12200160415121876738ULL ) ; // sanity check } { const auto start = std::clock() ; const auto result = fib_iterative(n) ; const auto end = std::clock() ; std::cout << "fib_iterative(" << n << ") == " << result << '\n' << (end-start) * 1000.0 / CLOCKS_PER_SEC << " milliseconds\n" ; assert( fib_iterative(93) == 12200160415121876738ULL ) ; // sanity check } }

http://rextester.com/KAL43202
Note that with the Microsoft library, the resolution of std::clock() is coarser;
it didn't tick even once for either of the two versions.
Recursion works just fine for this sequence (thanks @Enoizat). Since the sequence can go up (a lot) as well as down, it can unfortunately overflow, whether that uses recursion or a loop.

 123456789101112131415161718192021222324252627282930 #include #include using namespace std; using INT = int; // Worth testing the different types //using INT = unsigned long long; INT oddLimit = ( numeric_limits::max() - 1 ) / 3; //====================================================================== void palooka( INT n ) { cout << n << '\n'; if ( n != 1 ) { if ( n % 2 == 0 ) palooka( n / 2 ); else if ( n > oddLimit ) cout << "Sequence will overflow" << '\n'; else palooka( 3 * n + 1 ); } } //====================================================================== int main() { INT n; cout << "Input n: "; cin >> n; palooka( n ); }

 Input n: 113383 113383 340150 170075 510226 255113 --- many lines removed --- 1103160598 551580299 1654740898 827370449 Sequence will overflow

 Input n: 113384 113384 56692 28346 14173 42520 21260 10630 --- many lines removed --- 10 5 16 8 4 2 1

If we are to check the user's input then we should worry also whether he has entered a negative, something overflowing an integer, or even something non-numerate. So let's just assume the user has put in something legitimate.

Worrying about how one should divide by 2 in code is crass in the extreme.
Last edited on
@JLBorges,

your example for computing a Fibonacci number recursively is very different than the one I provided, it is written so the number of function recursions is significantly reduced compared to what my example requires.

Something a good, experienced programmer would do as a matter of course.

Computing the Fibonacci number for 20, your example takes 20 function recursions.

My example takes 21891 function recursions. That is considerable overhead.

Which is what I was saying. Recursion CAN BE, not ALWAYS IS, annoying and a headache in terms of performance.
Last edited on
> your example for computing a Fibonacci number is very different than the one I provided,

It is a recursive implementation of the same algorithm that was used in the iterative version.

I did mention: if the same algorithm is implemented, with one version being recursive and the other being iterative ...

> My example takes 21891 function recursions. That is considerable overhead.

If that is the case, you should also write an equivalent iterative version that performs 21891 iterations.
I would suspect that that would also have a significant overhead.

Comparing the performance of iterative heap sort and recursive heap sort would be meaningful.

Comparing the performance of an iterative heap sort with a recursive bubble sort won't prove that iteration is significantly faster than recursion for a sort operation. Nor would comparing the performance of an iterative bubble sort with a recursive heap sort prove that recursion is significantly faster than iteration for a sort operation.

> Recursion CAN BE, not ALWAYS IS, annoying and a headache in terms of performance.

Performance of recursive implementations would be a concern when non-trivial destructors of local objects are involved and/or when exceptions are a possibility. It would also be a concern when the problem demands that the number of iterations (which would be equal to the number of recursive calls) must necessarily be huge.

However, recursion is never annoying; it almost always is more elegant that an equivalent iterative implementation.
easily repeatable version; limited to integer ranges -- exits if overflow.
 1234567891011121314151617181920212223242526272829 #include using namespace std; int main() { int n; while (true) { cout << "Enter a positive number (0 to exit): "; cin >> n; if (n<=0) break; while (n!=1) { n = (n&1 ? n*3+1 : n/2); cout << n << endl; if (n<=0) { cout << "Overflow\n"; break; } } } cout << "\nBye!\n"; return 0; }

In action: https://repl.it/repls/ImpressiveFinancialRuntimeerror
Last edited on
icy1 wrote:
exits if overflow

Actually it doesn't.

Try n=2147483621 ... that OUGHT to overflow (for 4-byte ints).
The first few numbers will come out wrong. Check them by hand.
Signed integer overflow engenders undefined behaviour.

If control reaches line 14, n must be greater than zero and the if statement starting at line 18 may simply be optimised away as dead code (the optimiser simply assumes that signed integer overflow can never occur).

For example, both foo and bar could generate identical code:

 123456789101112131415161718192021222324 int foo( int n ) { if( n <= 0 ) return 5 ; n = (n&1 ? n*3+1 : n/2); if( n < 0 ) return -1 ; // this can never happen // or in other words, if this (signed integer overflow) // could happen, the entire program is already meaningless else return 1234 ; /* optimised to: if( n <= 0 ) return 5 ; else return 1234 ; */ } int bar( int n ) { if( n <= 0 ) return 5 ; else return 1234 ; }

https://godbolt.org/g/whxj4B
lastchance wrote:
Actually it doesn't.

Try n=2147483621 ... that OUGHT to overflow (for 4-byte ints).
The first few numbers will come out wrong. Check them by hand.

Ah, true, very nice catch ;P
For sufficiently big (odd) numbers, multiplying by 3 could produce a positive integer even after overflow
 12 >> (2147483621 * 3 ) - 2**32 => 2147483567

and then we add 1 to this, so that's why we get 2147483568. Makes sense; my checking for less than zero was incorrect -- your idea to check its value against a limit in advance is sounder.
Topic archived. No new replies allowed.