Number system base M, print numbers N digits wide...

Quote:

---

Let m be an integer, greater than zero but less than eleven. Numerical strings, in which each digit is greater or equal to 0 but less than m, are numbers of the number system in the base m. The numbers 10110 and 1981, for example, are numbers of the number system in the base the 10, but only the first one is a number of the number system in the base 2. The zeros at the beginning of the number are leading zeros, unless the number is 0.

Write a program that reads the integers m and n, and outputs all numbers of the number system in the base m containing n digits at the most, and without leading zeros. Each number may be output only once.

You may assume that m is greater than 0, but less than 11, and that n is greater than 0 but less than 81.

The numbers should be output on consecutive lines, one number per line.

---

I've been banging my head over this problem since last week, and i'm no closer to an answer than i was when i started.

I find myself always coming back to the idea of implementing a bidimensional array as such: nsys[n][m]

But i can't figure out the system of loops and conditions that would correctly solve this problem.

I'm hopelessly stuck. I'll keep banging my head, but i doubt i'll answer this.

I thought i'd ask for some help. Some clever hints would be better than the straight answer, as i would like to figure out as much of it by myself as i can. But i really need help.

Thanks...

adios,
biterma.

Just a thought:

declare a character string of size n, and then use something like a recursive function:

FUNCTION COUNTER (integer string_position)
counter = 0
WHILE counter < m
IF(string_position < n) THEN
CALL FUNCTION COUNTER(string_position + 1)

output_string[string_position] = counter converted to a character

counter = counter + 1

PRINT output_string
LOOP

I doubt that logic is exactly right, but maybe it gives an idea...? Good luck. It's an interesting problem.

>You may assume that m is greater than 0, but less than 11, and that n is greater than 0 but less than 81.

If not for these conditions, it would be straightforward. But the assumption that n is greater than 0 but less that 81 makes it difficult. 10^81 is a huge number, much too big for a float or double.

....which is why treating it as a string of text is probably your best bet. The algorithm is simple conceptually:

print out the digits from 0 to m in the "ones" column of the string

when you get to m, increment the "tens" (or fives, or whatever) column and then start over in the "ones" column

when the "tens" column gets to m, increment the next column and start over in the tens... ad infinitum... (ad nauseum?)...

Yes, good idea. Use a character array, initiialize it to '0's, and simulate adding one to get to the next number.

I don't know if you're allowed to do this, but there are m^n different possibilities. So you make a string n characters wide, and make a loop that runs m^n times; inside, you use this function called itoa, it goes like this

char *itoa(char* string, int number, int radix);

this function stores the specified number number, into string, using radix as the base, and it returns a pointer to the string (you don't need to use this one)

and then you print the string

if you do it like this, your problems will be solved, but maybe you're not allowed to use these "tricky" functions, so, if he/she's a computer science teacher(I'm supposing you need it as some kind of homework), you say that the function is ANSI-compliant. But if he/she's a math teacher, you have to do your own function, which is not really hard, but it's recommended that you use this one).

The other possibility is that I solved a completely different problem. In this case, tell me so.

I realise that people have kinda said the same thing before.. but here goes...

Code:

---

1. Create a data structure, myStructure to represent n digits.
(I believe that an array of integers is the best way to do this...)

2. Initilize myStructure to 0
3. while (!overflow(myStructure))
4. { printStructure(myStructure);
5.    incrementStructure(myStructure);}

---

And the incrementStructure function would be done using carrys and whatnought.

So basically your output would be something like this... (using base 3, with 3 digits...)

Quote:

---

000 001 002 010 ... 221 222

---

Although since the assignment only requires that you display all the different possibilities, it might be easier to do it this way

Quote:

---

000 100 200 010... 122 222

---

Finally, I should point out that I'm using the term structure here quite liberally. I wouldn't suggest actually using
stuct bleh { stuff; }
Just use an array of ints. It will make it easy to do the math and print.

This is not homework, it's just a problem i picked up from the net. It belongs to last years admissions exam to the Department of Computer Science of the University Of Helsinki. I'm just doing the exam for fun, since i'd like to apply there next year. Here's the URL: http://www.joensuu.fi/tkt/teh_eng.htm

Anyways, you can't use library functions except for standard I/O.

I thank you all, very much for your help.

I'll probably continue to ask for help from you, since i'm not really sure how use your advice.

Thanks again.

adios,
biterman.

PS: Btw, QuestionC, i can't have trailing zeros ;(

Well, you could arrange it so that the function you use to print doesn't print any leading zeroes.

Let me try to be a little more elaborate.

Code:

---

#include <stdio.h>
int main ()
{
 int intArray[82];
 int m, n;
 // m = base
 // n = digits
 
 scanf ("%d%d", &m, &n);
 
 // makes n values in the array 0, maybe n + 1 values?
 zeroIt (intArray, n);

 // Detects whether the array has overflowed
 while (!overflowIt (intArray, n))
 {
  // prints the values in the array from intArray[0...n-1]
  // shouldn't matter if we start at the end or beginning of array
  // skip leading zeroes
  printIt (intArray, n);

  putchar ('\n');

  // increases the value represented by 1
  // we have to pass it the base so it knows how to carry
  // shouldn't matter if we start at the end or beginning of array
  incIt (intArray, m);
 }
 return 0;
}

---

Of course, those functions will have to be implemented, but that is quite exactly the main function that I would use.

Your answer is beautiful, simply beautiful. You've managed to give me an incredible amount of advice without actually telling me how to do it. Tosi loistava! Hehe ;)

One thing though, i don't know what you mean by carry.

Code:

---

  // increases the value represented by 1
  // we have to pass it the base so it knows how to carry
  // shouldn't matter if we start at the end or beginning of array
  incIt (intArray, m);

---

Thanks a million.

adios,
biterman.

If think about how adding numbers is done with pencil and paper, this is how to do it. Take an integer array with each element representing a single digit, and use the same technique.

If you need to see some code, let me know, as I found the problem interesting enough to try.

I finally did it. Alot of people suggested an array of chars, and handling it all as a string, but i could'nt figure out how to do that. So i just did it the following way. Besides, since it's a test problem, you can only use standard input output functions, anything else is strictly prohibited.

So here's how i did it. Thanks to everyone who helped :)

Code:

---

/*
 * Problem 06
 * Print numbers n digits wide of number system base m
 */

#include <stdio.h>

int main(void)
{
        /* Main variables */
        /* m = base; n = digits */
        int m, n;
       
        /* Counter variables */       
        int i, j, k;
       
        /* Accept values of m & n only if within limits specified */
        do
        {
                printf("\nEnter m (0 < m < 11): ");
                scanf("%d", &m);
        }
        while(m < 1 || m > 10);
       
        do
        {
                printf("\nEnter n (0 < n < 81): ");
                scanf("%d", &n);
        }
        while(n < 1 || n > 80);
       
        /* Catch the wretched '\n' scanf() is so fond of leaving behind */
        getchar();
        /* Plainly esthetic '\n' */
        putchar('\n');
       
        /* Array to hold the numbers */
        int nsys[n];
       
        /* Initialize the entire array to zero */
        for(j = 0; j < n; j++)
                nsys[j] = 0;
       
        /* Iteration counter */
        k = 0;
       
        /* Special case: Unary System */
        if(m == 1)
        {
                printf("\nSpecial case - Unary System\n");               
                while(1)
                {
                        /* Find the last array index that is not already 1 */
                        for(j = (n-1); nsys[j] == 1 && j >= 0; j--)
                                ;
                        /* If they are all already one then we are all done */
                        if(j < 0)
                                exit(0);
                        else
                        {
                                /* Set it to 1 */
                                nsys[j] = 1;
                                /* Print everything thereafter */
                                while(j < n)
                                        printf("%d", nsys[j++]);
                                putchar('\n');
                       
                                /* Pause every ten iterations */
                                if(k++ == 9)
                                {
                                        k = 0;
                                        printf("\nPress any key to Continue or Ctrl-Break to Quit.\n");
                                        getchar();
                                }
                        }
                }
        }
       
        else
        {
                /* Where m > 1 */
                for(i = (n-1); 1;)
                {
                        /* Find the first nonzero array index */
                        for(j = 0; nsys[j] == 0 && j < (n-1); j++)
                                ;
                        /* Print everything thereafter */
                        /* The first time around this will just print the last array index */
                        while(j < n)
                                printf("%d", nsys[j++]);
                        putchar('\n');
               
                        if(nsys[i] == (m-1))
                        {
                                /* Find the last array index less than (m-1) */
                                for(j = i; nsys[j] == (m-1) && j >= 0; j--)
                                        ;
                                /* If there is not one then we are all done */
                                if(j < 0)
                                        break;
                                else
                                {
                                        /* Increase it and set everything thereafter to zero */
                                        nsys[j]++;
                                        j++;
                                        while(j < n)
                                                nsys[j++] = 0;
                                        /* Set last array index back to (m-1) */
                                        nsys[i] = (m-1);
                                }
                        }
               
                        /* Increase the last array index (units) */
                        if(nsys[i] < (m-1))
                                nsys[i]++;
                        else
                                nsys[i] = 0;
               
                        /* Pause every ten iterations */
                        if(k++ == 9)
                        {
                                k = 0;
                                printf("\nPress any key to Continue or Ctrl-Break to Quit.\n");
                                getchar();
                        }
                }
        }
        return 0;
}

---

I changed this:

Code:

---

/* Increase it and set everything thereafter to zero */
nsys[j]++;
j++;
while(j < n)
    nsys[j++] = 0;
/* Set last array index back to (m-1) */
nsys[i] = (m-1);

---

To this:

Code:

---

/* Increase it and set everything thereafter to zero */
/* Except the last array index (units) */
nsys[j]++;
j++;
while(j < i)
        nsys[j++] = 0;

---