All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Spirals (Posted on 2003-08-21)
Write a program (or explain how to do it) that will display a descending "spiral" of NxN numbers, using constant space (no arrays allowed). For example, here's what the spiral looks like for N=10:
```   99    98    97    96    95    94    93    92    91    90
64    63    62    61    60    59    58    57    56    89
65    36    35    34    33    32    31    30    55    88
66    37    16    15    14    13    12    29    54    87
67    38    17     4     3     2    11    28    53    86
68    39    18     5     0     1    10    27    52    85
69    40    19     6     7     8     9    26    51    84
70    41    20    21    22    23    24    25    50    83
71    42    43    44    45    46    47    48    49    82
72    73    74    75    76    77    78    79    80    81
```

 Submitted by DJ Rating: 4.4167 (12 votes) Solution: (Hide) I did this by numbering the rows going down and the columns across, from 0 to n-1. The square can be divided into four sections along the diagonals. Also, the NW-SE diagonals are composed of perfect squares, if you include the n² term 'hidden' to the left of (0, 0). Without going into much detail, I used these squares and the offsets along each row or column to come up with four if statements to define the value in terms of r and c. Here a small C++ program, that takes as input the value for n, then loops through to draw the spiral for that n: ```#include #include using namespace std; void main() { int n, r, c, x; cout << "n="; cin >> n; cout << endl; for (r=0; r=-1) && (c+r+1<=n)) x=(n-2*r)*(n-2*r)-1-c+r; else if ((c-r>-1) && (c+r+1>n)) x=(2*c-n+1)*(2*c-n+1)+c-r; else if ((c-r<=-1) && (c+r+1>=n)) x=(2*r-n+1)*(2*r-n+1)+c-r; else x=(n-2*c-2)*(n-2*c-2)-1-c+r; cout << setw(n<11 ? 3 : 4) << x; } cout << endl; } } ``` Some sample outputs: ```n=5 24 23 22 21 20 9 8 7 6 19 10 1 0 5 18 11 2 3 4 17 12 13 14 15 16 n=10 99 98 97 96 95 94 93 92 91 90 64 63 62 61 60 59 58 57 56 89 65 36 35 34 33 32 31 30 55 88 66 37 16 15 14 13 12 29 54 87 67 38 17 4 3 2 11 28 53 86 68 39 18 5 0 1 10 27 52 85 69 40 19 6 7 8 9 26 51 84 70 41 20 21 22 23 24 25 50 83 71 42 43 44 45 46 47 48 49 82 72 73 74 75 76 77 78 79 80 81 n=15 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 169 168 167 166 165 164 163 162 161 160 159 158 157 156 209 170 121 120 119 118 117 116 115 114 113 112 111 110 155 208 171 122 81 80 79 78 77 76 75 74 73 72 109 154 207 172 123 82 49 48 47 46 45 44 43 42 71 108 153 206 173 124 83 50 25 24 23 22 21 20 41 70 107 152 205 174 125 84 51 26 9 8 7 6 19 40 69 106 151 204 175 126 85 52 27 10 1 0 5 18 39 68 105 150 203 176 127 86 53 28 11 2 3 4 17 38 67 104 149 202 177 128 87 54 29 12 13 14 15 16 37 66 103 148 201 178 129 88 55 30 31 32 33 34 35 36 65 102 147 200 179 130 89 56 57 58 59 60 61 62 63 64 101 146 199 180 131 90 91 92 93 94 95 96 97 98 99 100 145 198 181 132 133 134 135 136 137 138 139 140 141 142 143 144 197 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 ``` Also, Your Buddy and Charlie offered alternate algorithms in the problem comments.

 Subject Author Date Another solution!! phenomenon 2004-02-21 02:53:41 Recursive AJ 2003-09-05 01:02:47 Neat Adam Sisco 2003-08-23 10:13:16 re(3): solution Your buddy 2003-08-21 17:28:26 re(2): solution Charlie 2003-08-21 16:54:31 re(2): FULL SOLUTION (in C) Charlie 2003-08-21 16:51:49 re: solution Charlie 2003-08-21 16:39:35 solution Charlie 2003-08-21 16:36:43 re: FULL SOLUTION (in C) Your buddy 2003-08-21 15:55:56 FULL SOLUTION (in C) Your buddy 2003-08-21 15:50:00

 Search: Search body:
Forums (0)