Advanced Search

Ternary Counting In C

/ Published in: C
Save to your folder(s)
Here's a fairly useless but fun piece of code: counting in base 3. This takes in a number of digits and counts up in ternary. Be warned, though. The algorithm is (for obvious reasons) O(n^3), where n is the number of digits. Actually probably theta(n^3), since n^3 is both the upper and lower bound. Either way, it spits out 531,441 possibilities for 12 digits, so be careful not to run it on too many digits.

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. int countInTernary(int numdigits) {
  2.     char num[numdigits+1];
  3.     memset(num, '0', sizeof num);
  4.     num[numdigits] = 0;
  5.     char *curIndex = &num[numdigits-1];
  6.     char *end = &num[numdigits-1];
  7.     char *start = &num[0];
  8.     bool done = false;
  9.  
  10.     while (!done) {
  11.         printf("%s\n", num);
  12.         if (*curIndex < '2') {
  13.             (*curIndex)++;
  14.         } else {
  15.             /* move left until you find a number < 2 */
  16.             while (curIndex >= start && *curIndex == '2') {
  17.                 --curIndex;
  18.             }
  19.             if (curIndex < start) {
  20.                 done = true;
  21.             } else {
  22.                 (*curIndex)++;
  23.                 while (curIndex < end) {
  24.                     curIndex++;
  25.                     *curIndex = '0';
  26.                 }                
  27.             }
  28.         }
  29.     }  
  30.     return EXIT_SUCCESS;
  31. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.