A programozó munkája a legkönnyebb /2

Legyen egymasra meroleges 7 piros vonal! De zold es atlatszo tintaval!

Nézd meg hogy az `ls -v` mit csinál. Nekem úgy tűnik hogy az is a kevesebb oszlopra szavaz.

Az alternatív specifikáció ötleted nekem nem tetszik, nem tűnik tipikus, jól ismert viselkedésnek.

Jó feladat. Az a helyzet, hogy nincs mindig megoldása. Ugyanis amit valójában elvársz, az a következő: azt várod el, hogy az első maradékos osztás adjon nulla maradékot, vagy a második maradékos osztás adjon nemnulla maradékot. (Ezeket a maradékos osztásokat mindjárt leírom formálisan is.) És van olyan n és c, hogy egyik elvárás sem teljesül.

Tehát formálisan (az alábbiakban n, c, q, q2, r és r2 mind egész számok):

1. Első körben azt a maradékos osztást nézed, hogy n = q * c + r, ahol adott n>0 a tételek száma, adott c>0 a teljes oszlopok száma, keresett q>=0 a hányados (sorok száma a teljes oszlopokban), és keresett c>r>=0 a maradék (az utolsó, nem teljes oszlopban lévő sorok száma -- maradék lévén ez kisebb, mint az osztó; ha már annyi sor szerepelne az utolsó, nem teljes oszlopban, mint ahány teljes oszlop van, akkor a hányados nőne meg, vagyis eggyel több sor lenne a teljes oszlopokban).

   Első körben azt várod el, hogy r=0 legyen; ekkor kapsz egy szép mátrixot, pontosan c oszloppal, és q sorral. (És ekkor rögtön adódik az is, hogy q pozitív, hiszen n = q * c.)

   Ha viszont r>0 adódik, akkor van egy nem teljes utolsó oszlopod is, amivel megszegted az "oszlopszám=c" elvárást, tehát át kell térnünk eggyel kisebb oszlopszámra ((c-1)-re). Itt rögtön látjuk azt is, hogy ebben az esetben c>=2 (tehát (c-1) még mindig pozitív lesz); ugyanis ha az eredeti osztó c=1 volt (összesen 1 oszlopot kértünk), akkor q=n (n sorunk lesz) és r=0 (nincs maradék -- nincs nem teljes oszlop) -- vagyis c=1 esetén nem jutottunk volna ide (ahol r>0).
    

2. Második körben azt a maradékos osztást nézzük, hogy n = q2 * (c-1) + r2, ahol adott n>0 továbbra is a tételek száma, adott (c-1)>0 az oszlopok (eggyel csökkentett, de a fentiek szerint még mindig pozitív) száma, keresett q2>=0 hányados (a sorok száma a teljes oszlopokban), és keresett (c-1)>r2>=0 maradék (az utolsó, nem teljes oszlopban lévő sorok száma).

   Pontosabban (és ezen bukik a dolog): itt azt várjuk el, hogy r2>0 legyen. Ugyanis ha r2=0, akkor nincs betöltetlen oszlop, és kapunk egy szép mátrixot (c-1) oszloppal és q2 sorral -- ami viszont ismét megszegi az eredeti "oszlopszám=c" elvárást.

Vagyis a sejtésed az (más szóval: a specifikáció feltételezése az), hogy:

∀ n, c ∈ ℕ⁺: (∃ q ∈ ℕ⁺: n = q * c) ∨ (∃ q₂ ∈ ℕ, (c - 1) > r₂ ∈ ℕ⁺: n = q₂ * (c-1) + r₂)

Mivel ez egy olyan elsőrendű logikai állítás, amely univerzális kvantorral kezdődik, azért a cáfolatához elég egy ellenpéldát találni. Formálisan, a sejtés negáltja úgy néz ki, hogy először az egész elé kiragasztunk egy tagadást:

¬∀ n, c ∈ ℕ⁺: (∃ q ∈ ℕ⁺: n = q * c) ∨ (∃ q₂ ∈ ℕ, (c - 1) > r₂ ∈ ℕ⁺: n = q₂ * (c-1) + r₂)

Aztán a logikai "nem" operátort bevisszük az univerzális kvantoron belülre (amitől az egzisztenciális kvantorrá változik, a kvantált predikátum pedig negálódik):

∃ n, c ∈ ℕ⁺: ¬((∃ q ∈ ℕ⁺: n = q * c) ∨ (∃ q₂ ∈ ℕ, (c - 1) > r₂ ∈ ℕ⁺: n = q₂ * (c-1) + r₂))

Azután a De Morgan azonossággal a negálást szétosztjuk a logikai "vagy"-on (amitől a "vagy" "és"-sé változik, az operandusai pedig negálódnak):

∃ n, c ∈ ℕ⁺: ¬(∃ q ∈ ℕ⁺: n = q * c) ∧ ¬(∃ q₂ ∈ ℕ, (c - 1) > r₂ ∈ ℕ⁺: n = q₂ * (c-1) + r₂)

Ismét a kvantoros játék:

∃ n, c ∈ ℕ⁺: (∀ q ∈ ℕ⁺: n ≠ q * c) ∧ (∀ q₂ ∈ ℕ, (c - 1) > r₂ ∈ ℕ⁺: n ≠ q₂ * (c-1) + r₂)

Ha ezt az állítást sikerül kielégíteni, akkor a sejtést megcáfoltuk.

Az általad adott n=18, c=7 számpár "létezik", és kielégíti a sejtés negáltját; vagyis cáfolja a sejtést:

(∀ q ∈ ℕ⁺: 18 ≠ q * 7) ∧ (∀ q₂ ∈ ℕ, 6 > r₂ ∈ ℕ⁺: 18 ≠ q₂ * 6 + r₂)

Ennek a konjunkciónak mindkét operandusa igaz, ugyanis:

• a 18 nem osztható 7-tel (bármely pozitív egésszel szorozzuk a 7-et, nem lesz a szorzat 18), valamint
• a 18-at 6-tal osztva 0 a maradék, ami pedig nem eleme az ℕ⁺ halmaznak (ha q₂ értéke 0, 1 vagy 2, akkor r₂ értéke rendre 18, 12, 6, amelyek egyike sem elégíti ki a 6>r₂ követelményt; ha q₂ értéke 3, akkor r₂=0, ami nem eleme az ℕ⁺ halmaznak; ha pedig q₂>3, akkor r₂ negatív, így nem eleme az ℕ⁺ halmaznak).

Összefoglalva: pontosan c oszloppal nem mindig megoldható a feladat; lehet, hogy (c-1) oszlopú mátrixot fogsz kapni. És ez az eset akkor áll fenn, ha c nem osztója n-nek, (c-1) viszont osztója n-nek.

Ha emberi sorrendben írod ki (balról jobbra), akkor látszik, hogy miért nincs megoldás, mert több hasáb lesz hiányos: 

 1  2  3  4  5  6  7

 8  9 10 11 12 13 14

15 16 17

De akkor meg csak hat oszlopom van.

Ez nem igaz, a feladat sehol nem kötötte ki, hogy egy oszlopban minimum 1 tételnek kell lennie. Nem is kötheti ki, mert ha N az osztó akkor a maradék 0 és N-1 közé kell, hogy essen. Vagyis továbbra is 7 hasáb van, csak az utolsó hasáb, vagyis a maradék 0 tételt tartalmaz.

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.

#include <stdio.h>
#include <stdlib.h>

void draw(int num, int col, int row)
{
  int i, j, n;
  printf("    |");
  for (j = 0; j < col; ++j) printf("#%-3i|", j+1);
  printf("\n");
  for (i = 0; i < row; ++i)
  {
    printf("#%-3i|", i+1);
    for (j = 0, n = i; j < col; ++j, n += row)
      (n < num) ? printf("%4i|", n) : printf("   -|");
    printf("\n");
  }
}

void calc(int num, int inp_col, int *out_col, int *row)
{
  int m;
  *out_col = inp_col;
  m = num % inp_col;
  *row = num / inp_col;
  if (m == 0) return;
  (*row)++;
  if (inp_col - m < *row) return;
  *out_col = num / *row;
  if (num % *row > 0) (*out_col)++;
}

int main(int argc, char *argv[])
{
  int an,ac,r,c;
  an = atoi(argv[1]);
  ac = atoi(argv[2]);
  calc(an, ac, &c, &r);
  if (ac != c) printf("Nem oldhato meg %i oszlopban\n", ac);
  printf("Megoldhato %i oszlopban, %i sor\n", c, r);
  draw(an, c, r);
  return 0;
}