Magic square program 
Author Message
 Magic square program

        Does anyone have any insight on the "Magic square" program
that is frequently assigned to beginning C programmers?  The program
seems simple enough to me, exept I cannot figure out how to use MALLOC
to declare an unknown sized array to hold all of my values.  Any
clues?  Thanks.



Wed, 14 Oct 1998 03:00:00 GMT  
 Magic square program

|        Does anyone have any insight on the "Magic square" program
|that is frequently assigned to beginning C programmers?  The program
|seems simple enough to me, exept I cannot figure out how to use MALLOC
|to declare an unknown sized array to hold all of my values.  Any
|clues?  Thanks.

I love magic squares ... As a matter of fact, you don't need to malloc
anything to produce a simple (odd sized) magic square; even more, you
don't need any memory proportional to the dimension of the magic square
at all if you just want to print out the result. Lets have a look at an
inituitive method producing such a square:

1: start in the middle row and rightmost column. Put a '1' in this cell;
2: if all cells contain a number; stop;
3: move south-east, i.e. one cell to the right and one down. Wrap around
   whenever necessary;
4: if this cell is not occupied yet, put the next number there and
   go to step 2;
5: otherwise, instead of moving south-east, move west and go to step 2.

Here's a 5*x5 magic square produced by the method described above:

        11   10    4   23   17
        18   12    6    5   24
        25   19   13    7    1
         2   21   20   14    8
         9    3   22   16   15

And here's the fun part; in comp.programming is a debate going on whether
or not math is necessary in programming. My (humble) opinion is yes,
simple math can come in quite handy when one has to spend (too) much time
in front of one of those silly screens and keyboards (I don't consider
a mouse a serious computer device; it reduces the user of it to a druling
idiot who races that silly thing all over his/her desk back and forth
like a dinky toy ;-).

Here's the math stuff: if the size of the square equals n*n, then the
number in the middle cell of the square equals (n*n+1)/2 and consequently,
the number in the top-left cell equals (n*n+1)/2-(n-1)/2 = (n*n-n+2)/2.

Any number in the leftmost column is one greater than the number in the
row above in the rightmost cell.

If a number 'i' in a cell equals 0 mod n, then the number to the left of it
(if present) equals i+1; that's the number we've bumped in to in step 4 and
step 5 of the method described above. Otherwise the number to the left of it
equals i+n+1 (modulo n*n, that is).

Just because I'm babbling in comp.lang.c here, here's a simple C function
that does the job for you:

void msquare(int n) {

int row, col, num;

num= (n*n-n+2)/2;                     /* Top left cell */

for (row = 1; row <= n; row++)        /* For all rows ... */
   for (col= 1; col <= n; col++) {    /* For all columns ... */

   printf("%4d ", num);               /* Print current cell */

   if (col != n) {                    /* Not on last column? */

      if (num%n == 1)                 /* Subtract one allowed? */
         num--;
      else                            /* Next diagonal */
         num-= (n+1);

      if (num < 1)                    /* Adjust for wrap around */
         num+= n*n;

   }
   else {                             /* Last column reached */
      num++;                          /* Adjust for new row */        
      printf("\n");
   }

Quote:
}
}

But if you insist wasting memory by using malloc(), here's a way to do it:

int**   sqmalloc(int n) {

int**   mat;
int     i;

mat= malloc(n*sizeof(int*));    /* allocate pointers for all rows;

*mat= malloc(n*n*sizeof(int));  /* allocate the matrix itself */

for (i= 1; i < n; i++)               /* set all row pointers */
        mat[i]= mat[i-1]+n;

return mat;                     /* here you are */

Quote:
}

kind regards,


--
Atnwgqkrl gy zit vgksr, ug qshiqwtzoeqs!



Wed, 14 Oct 1998 03:00:00 GMT  
 Magic square program

Quote:

>        Does anyone have any insight on the "Magic square" program
>that is frequently assigned to beginning C programmers?  The program
>seems simple enough to me, exept I cannot figure out how to use MALLOC
>to declare an unknown sized array to hold all of my values.  Any
>clues?  Thanks.

void foo(int nelems)
{
    int *ptr;

    if ((ptr = malloc(nelems * sizeof(*ptr)) == NULL) {
        /* Deal with allocation failure */
    }

    /* Here you can use ptr[0] through to ptr[nelems-1] which start
       uninitialised. When you've finished with the array: */

    free(ptr);

Quote:
}

For more infortation including how to simulate dynamic 2D arrays see the
FAQ available via ftp from rtfm.mit.edu under /pub/usenet/comp.lang.c

--
-----------------------------------------


-----------------------------------------



Wed, 14 Oct 1998 03:00:00 GMT  
 Magic square program

|>  
|>
|>   Does anyone have any insight on the "Magic square" program
|> that is frequently assigned to beginning C programmers?  The program
|> seems simple enough to me, exept I cannot figure out how to use MALLOC
|> to declare an unknown sized array to hold all of my values.  Any
|> clues?  Thanks.

Ever heard of linked list?  One of the simplest ways to make an unknwon sized
array is by linked list.  Or if you don't bother with the detail, use a very
large fix size array!



Fri, 16 Oct 1998 03:00:00 GMT  
 Magic square program

Quote:

>>        Does anyone have any insight on the "Magic square" program
>> that is frequently assigned to beginning C programmers?  The program
>> seems simple enough to me, except I cannot figure out how to use MALLOC
>> to declare an unknown sized array to hold all of my values.  Any
>> clues?  Thanks.

> Ever heard of linked list?  One of the simplest ways to make an unknown
> sized array is by linked list.  Or if you don't bother with the detail,
> use a very large fix size array!

For an unknown, but fixed size once known, array I'd say just dynamically
allocate it. However, for an unknown and unfixed size data structure a
list may not be a bad idea. Since your program is a "square" this probably
calls for a 2D array. See the FAQ on how to dynamically allocate one of these.
You'll learn alot!
--
"If it wasn't for C, we would be using BASI, PASAL, and OBOL."




Sat, 17 Oct 1998 03:00:00 GMT  
 Magic square program



Quote:

>|>      
>|>
>|>      Does anyone have any insight on the "Magic square" program
>|> that is frequently assigned to beginning C programmers?  The program
>|> seems simple enough to me, exept I cannot figure out how to use MALLOC
>|> to declare an unknown sized array to hold all of my values.  Any
>|> clues?  Thanks.

>Ever heard of linked list?  One of the simplest ways to make an unknwon sized
>array is by linked list.

I suppose you could in theory simulate an array with a linked list. However
access to an arbitrary element would be O(n) rather than O(1) and it
certainly isn't a sensible approach in this case (and probably not in
general). malloc is the way to allocate arrays whose size is determined
at runtime. For simulation of 2D arrays see the FAQ.

--
-----------------------------------------


-----------------------------------------



Sat, 17 Oct 1998 03:00:00 GMT  
 Magic square program

Quote:


> > Ever heard of linked list?  One of the simplest ways to make an unknown
> > sized array is by linked list.  

Well, not quite.  A standard linked list won't let you just access any
abritrary element like an array.  You would have to keep track of the
pointers to each element.

seeya!

Reuven Lax



Sun, 18 Oct 1998 03:00:00 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Magic Square Programming

2. Magic square program solved - msquare.c (0/1)

3. Magic square program solved, part II

4. Magic square program solved - msquare.c (1/1)

5. Magic Square Problems???

6. Magic Square Problems???

7. Magic Squares source code

8. Magic Square Code??

9. Help: Magic Square using 2 dimensional array.

10. Magic Square..

11. I need help with a magic square

12. Help with magic squares code

 

 
Powered by phpBB® Forum Software