C question lol

[nothing]

How do I read and display a short int in C using scanf and printf? Thank you.

[fishybawb]

Like this:


short int test;
scanf("%hd", &test);
printf("You entered: %hd\n", test);


Got tired of the ++ part, eh? ;)

[nothing]

No! Well, maybe. I'm trying to solve these problems at http://acm.uva.es/problemset/ and I submitted the answer for problem number 100 in C++. My program was horrible; it took a lot of time to execute and used a lot of memory compared to other people's programs, specially the first on the rank. So I tried a C version. Same thing, just a little faster lol. I have no idea how those guys do that.

[ScaryBinary]

Here's an interesting thought:

The problem says that if n is odd, then n = 3n + 1. The trick here is that if n really is odd, 3n + 1 will always be even (you can do the proof yourself!). Thus, you can actually skip a loop when you come across an odd number, because you know that the result will be even, in which case your next step will be to divide by two (as in the problem statement). So really, if you get n % 2 != 0, you can just perform n = (3 * n + 1) / 2 and add 2 to your cycle length:

while(i <= j){
n = i;

while(n != 1){
if(n % 2 != 0) {
n = (3 * n + 1) / 2;
// Up cycle count here once,
// then once at end of loop since
// we just skipped a step.
cycle_length++;
}
else
n /= 2;

cycle_length++;
}

if(cycle_length > max_cycle_length)
max_cycle_length = cycle_length;

i++;
cycle_length = 1;
}
A shortcut that may shave a few microseconds off your time?

There is another shortcut I found, resulting in the fact that you can quit looping whenever you get to 32 or 5 (instead of 1), and then just add 6 to your cycle count. I think your last few numbers in the sequence will always be either [32, 16, 8, 4, 2, 1] or [5, 16, 8, 4, 2, 1]. You can start with your end result of 1 and work your way backwards through the algorithm....

If we ended up with 1, then 1 = n/2 or 1 = 3n + 1. This means n=2, or n = 0. n = 0 doesn't make sense, so n must have been 2. So now we have 2 = n/2 or 2 = 3n + 1. This means n=4, or n= 1/3. n can't be 1/3 since we only have integer values, so n must have been 4. Keep doing this and the first numbers you get to that can satisfy either equation are 32 (for n = n/2) and 5 (for n = 3n + 1). Just some dorky math tricks.

Boy, I have way too much free time. :D

[ScaryBinary]

Actually, the thing to do, I suppose, would be to stop when n=16, since that will catch both even and odd cases, and you only need one check (as oppose to checking for 5 or 32).

[nothing]

Hey, those are very neat ideas. I'll see if I can implement them into my program. Thanks!

[ScaryBinary]

The latter idea I posted (about stopping after n=16) may be more trouble than it's worth, but the code snippet I posted should shave a little processing time off.