Támadt egy új ötletem! :) (Bocsánat, ha valaki már írta a topicban.)
A táblázatban a helyeket (cellákat) töltsük fel sorfolytonosan, majd a megtalált cellákat az értékekkel töltsük fel oszlopfolytonosan!
Ennek az a szépsége, hogy tetszőleges (n>0, c>0) párra működik, és a kimenet jól néz ki, mert az összes oszlop majdnem ugyanolyan magas.
Ennek a "majdnem ugyanolyannak" itt a formális meghatározása (példa: n=27, c=5):
0 1 2 3 4
0 X X X X X
1 X X X X X
2 X X X X X
3 X X X X X
4 X X X X X
5 X X
n = q * c + r (q >= 0; c > r >= 0)
A q megadja a teli sorok számát, az r pedig megadja, hogy az utolsó, nem teli sorban hány maradék elem van. Ha r=0, akkor egy szép teli téglalapot kaptunk.
Ha pedig r>0, akkor mindig az az elrendezés, a sorfolytonos cellaválasztás következtében, hogy a bal oldalon található egy r oszlopból és q+1 sorból álló "A" téglalap, a jobb oldalon pedig egy c-r oszlopból és q sorból álló "B" téglalap:
0 1 2 3 4
0 A A B B B
1 A A B B B
2 A A B B B
3 A A B B B
4 A A B B B
5 A A
Aritmetikailag felírva a cellák számát az A és B téglalapokban:
r*(q+1) + (c-r)*q = r*q + r + c*q - r*q = c*q + r = n
Tehát jól számoltunk, valóban az n db cellát helyeztük el.
Ennek a felírásnak további szépsége az, hogy független attól, hogy r=0 vagy r>0. Ha ui. történetesen r=0, akkor az A téglalap szélessége egyszerűen 0 oszlop, a B téglalap szélessége pedig c-r = c-0 = c oszlop.
Akkor a cellákat elhelyeztük; hogyan töltsük fel azokat? Ugyanis printelni sorfolytonosan tudunk. Nem nehéz; minden sorban az induló érték (a 0. oszlop értéke) magának a sornak a száma. Ahogy jobbra haladunk az adott sorban, az értéket annyival kell megnövelnünk, mint az éppen elhagyandó oszlop magassága. Ha a jelenlegi oszlop száma (nullával kezdve a számozást) kisebb mint r, akkor ez a növekmény (vagyis az oszlop magassága) q+1, egyébként pedig q.
(Itt is látszik, hogy ha r=0, vagyis az osztás egzakt, akkor az "oszlop száma kisebb mint r" sosem teljesül, vagyis a növekmény mindig q.)
Itt a program:
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#define CELL_WIDTH 3
static int
get_positive_long(long *val, const char *str)
{
long tmp;
char *end;
errno = 0;
tmp = strtol(str, &end, 0);
if (end == str || *end != '\0' || errno != 0 || tmp <= 0) {
(void)fprintf(stderr, "invalid value: \"%s\"\n", str);
return -1;
}
*val = tmp;
return 0;
}
int
main(int argc, char **argv)
{
long num_val, num_col;
ldiv_t qr;
long row, col, val, i;
if (argc != 3) {
(void)fprintf(stderr, "usage: %s num_val num_col\n", argv[0]);
return EXIT_FAILURE;
}
if (get_positive_long(&num_val, argv[1]) == -1 ||
get_positive_long(&num_col, argv[2]) == -1) {
return EXIT_FAILURE;
}
if (num_val < num_col) {
(void)fprintf(stderr, "expected num_val(%ld) >= num_col(%ld)\n", num_val,
num_col);
return EXIT_FAILURE;
}
qr = ldiv(num_val, num_col);
row = col = val = i = 0;
for (;;) {
(void)printf("%*ld", CELL_WIDTH + (col > 0), val);
if (i == num_val - 1) {
(void)printf("\n");
break;
}
if (col < num_col - 1) {
val += qr.quot + (col < qr.rem);
++col;
} else {
(void)printf("\n");
val = ++row;
col = 0;
}
++i;
}
return EXIT_SUCCESS;
}
... Ja, tényleg, joco01 már említette a sorfolytonosságot.