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

  1. #1
    free(me);
    Join Date
    Oct 2001
    Location
    Santo Domingo, DN, Dominican Republic
    Posts
    98

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

    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.
    Do you know how contemptous they are of you?

  2. #2
    Unregistered
    Guest
    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.

  3. #3
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >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.

  4. #4
    Unregistered
    Guest
    ....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?)...

  5. #5
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    Yes, good idea. Use a character array, initiialize it to '0's, and simulate adding one to get to the next number.
    Last edited by swoopy; 11-14-2001 at 03:00 PM.

  6. #6
    Former Member
    Join Date
    Oct 2001
    Posts
    955
    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.

  7. #7
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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...)
    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
    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.
    Callou collei we'll code the way
    Of prime numbers and pings!

  8. #8
    free(me);
    Join Date
    Oct 2001
    Location
    Santo Domingo, DN, Dominican Republic
    Posts
    98

    ...

    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 ;(
    Last edited by biterman; 11-15-2001 at 01:39 AM.
    Do you know how contemptous they are of you?

  9. #9
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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.
    Callou collei we'll code the way
    Of prime numbers and pings!

  10. #10
    free(me);
    Join Date
    Oct 2001
    Location
    Santo Domingo, DN, Dominican Republic
    Posts
    98

    Question ...

    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.
    Do you know how contemptous they are of you?

  11. #11
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    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.

  12. #12
    free(me);
    Join Date
    Oct 2001
    Location
    Santo Domingo, DN, Dominican Republic
    Posts
    98

    I answered it...

    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;
    }
    Do you know how contemptous they are of you?

  13. #13
    free(me);
    Join Date
    Oct 2001
    Location
    Santo Domingo, DN, Dominican Republic
    Posts
    98

    ...

    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;
    Do you know how contemptous they are of you?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 03-05-2009, 10:25 AM
  2. Looking for constructive criticism
    By wd_kendrick in forum C Programming
    Replies: 16
    Last Post: 05-28-2008, 09:42 AM
  3. Replies: 3
    Last Post: 06-13-2005, 07:28 AM
  4. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM
  5. converting numbers from one base to another
    By partnole in forum C++ Programming
    Replies: 4
    Last Post: 10-04-2001, 12:29 PM