Friday, January 30, 2009

UVa problem 100: sample code, sample algorithm

UVa problem 100 (3n + 1) is a pretty straightforward problem. There is one tricky part though. That i is not necessarily always less than j. So one needs to watch out for the case when i is greater than or equal to j.

Also one, can speed things a little bit by using the bit-shift operator for division or multiplication. A division by 2 is similar to a right bit-shift by 1 bit. A multiplication by 2 is equivalent to a left bit-shift by 1 bit.

That is, x / 2 is equivalent to x >> 1; x * 2 is equivalent to x << 1.


001 #include "stdio.h"
002
003 int main() {
004 char line[100];
005
006 int i
007 , j
008 , n
009 , n0
010 , m
011 , cycle
012 , max
013 ;
014
015 while (fgets(line, 100, stdin)) {
016 sscanf(line, "%d %d", &i, &j);
017
018 if (i <= j) {
019 for (n0 = i, max = 1; n0 <= j; n0++) {
020 n = n0;
021 for (cycle = 1; n != 1; cycle++) {
022 m = n & 1;
023 if (m) {
024 m = n << 1;
025 n = m + n + 1;
026 }
027 else {
028 n >>= 1;
029 }
030 }
031 if (cycle > max) {
032 max = cycle;
033 }
034 }
035 }
036 else {
037 for (n0 = j, max = 1; n0 <= i; n0++) {
038 n = n0;
039 for (cycle = 1; n != 1; cycle++) {
040 m = n & 1;
041 if (m) {
042 m = n << 1;
043 n = m + n + 1;
044 }
045 else {
046 n >>= 1;
047 }
048 }
049 if (cycle > max) {
050 max = cycle;
051 }
052 }
053 }
054
055 printf("%d %d %d\n", i, j, max);
056 }
057
058 return 0;
059 }

No comments:

Post a Comment