Skaiciu grupes (C++)

Sveiki, neiseina parasyti algoritma vienai uzduociai, gal galeciau gauti pagalbos?

Duotas naturalusis skaicius N. Parasykite programa, kuri suskirstytu naturaliuosius skaicius 1..N kvadratu i N grupes ir butu tenkinamos tokios salygos:

1. kiekviena grupe butu sudaryta is N skaiciu;

2. kiekvienas skaicius priklausytu tik vienai grupei;

3. visu grupiu skaiciu sumos butu lygios.

PVZ:

Pradiniai duomenys: 4

Rezultatai:

1 6 11 16 34

13 2 7 12 34

9 14 3 8 34

5 10 15 4 34

34 - suma.

Mano parasytas algoritmas veikia tik iki 4, kai n > 4 nesudaro paskutiniu grupiu, nes nebelieka skaiciu, kurie sudarytu reikiama suma (lieka tik mazi skaiciai, kuriu nepakanka). Programa ima arba didziausia galima skaiciu arba maziausia, o paskutiniam grupes nariui ima toki, kokio reiks sumai. Kaip is anksto atrinkti tokius skaicius, kad skaiciai tiktu visoms grupems?

Sveikas. Pirmiausia pastebime, kad matricos įstrižainė yra 1, 2, ... , n . Nuo įstrižainės einant žemyn reikšmė mažinama nuo n*n - n + eilNr. O aukštyn - didinama. Viskas turėtų būti aišku, išnagrinėjus kodą.

P.S Reikia patikrinti ar įvestas n yra teigiamas skaičius. Bet tai jau palieku padaryti pačiam.

#include <iostream>

using namespace std;

int** fillMatrix(int n);
void printMatrix(int **m, int size);

int main()
{
cout << "Iveskite n ";
int n;
cin >> n;
cout << "\n";
int **m = fillMatrix(n);
printMatrix(m, n);
cin >> n;   // tik tam, kad neuzsidarytu konsoles langas
return 0;
}

int** fillMatrix(int n)
{
int **matrix = new int*[n];
for (int i = 0; i < n; i++)
	matrix[i] = new int[n];

for (int i = 0; i < n; i++)
{
	int nDiag = i + 1;
	matrix[i][i] = nDiag;

	for (int j = i - 1; j >= 0; j--)
	{
		nDiag = nDiag + n;
		matrix[i][j] = nDiag;
	}

	nDiag = n * n - n + i + 1;

	for (int j = i + 1; j < n; j++)
	{
		matrix[i][j] = nDiag;
		nDiag = nDiag - n;
	}

}
return matrix;
}

void printMatrix(int **m, int size)
{
for (int row = 0; row < size; row++)
{
	int sum = 0;
	for (int column = 0; column < size; column++)
	{
		sum += m[column][row];
		cout << m[column][row] << " ";
	}
	cout << "  sum = " << sum << "\n";
}
   return;
}

Sveikas. Pirmiausia pastebime, kad matricos įstrižainė yra 1, 2, ... , n . Nuo įstrižainės einant žemyn reikšmė mažinama nuo n*n - n + eilNr. O aukštyn - didinama. Viskas turėtų būti aišku, išnagrinėjus kodą.

P.S Reikia patikrinti ar įvestas n yra teigiamas skaičius. Bet tai jau palieku padaryti pačiam.

 

#include <iostream>

using namespace std;

int** fillMatrix(int n);
void printMatrix(int **m, int size);

int main()
{
cout << "Iveskite n ";
int n;
cin >> n;
cout << "\n";
int **m = fillMatrix(n);
printMatrix(m, n);
cin >> n;   // tik tam, kad neuzsidarytu konsoles langas
return 0;
}

int** fillMatrix(int n)
{
int **matrix = new int*[n];
for (int i = 0; i < n; i++)
	matrix[i] = new int[n];

for (int i = 0; i < n; i++)
{
	int nDiag = i + 1;
	matrix[i][i] = nDiag;

	for (int j = i - 1; j >= 0; j--)
	{
		nDiag = nDiag + n;
		matrix[i][j] = nDiag;
	}

	nDiag = n * n - n + i + 1;

	for (int j = i + 1; j < n; j++)
	{
		matrix[i][j] = nDiag;
		nDiag = nDiag - n;
	}

}
return matrix;
}

void printMatrix(int **m, int size)
{
for (int row = 0; row < size; row++)
{
	int sum = 0;
	for (int column = 0; column < size; column++)
	{
		sum += m[column][row];
		cout << m[column][row] << " ";
	}
	cout << "  sum = " << sum << "\n";
}
   return;
}

Aciu! Supratau kaip daryti. As dabar abiturientas, tai tavo sintakse man ne iki galo suprantama, bet pacia ideja pagavau. Gali i pora klausimu atsakyt?

1. Kam gale void funkcijos rasyti return?

2. Kam siusti pointerius, jei galima passinti funkcijose taip: "void printMatrix(int& m, int mas[])" ?

3. Kaip tu grazinai masyva per funkcija? Gal gali numesti suprantamesni tutoriala?

Trumpesnis variantas:

#include <iostream>

using namespace std;

int main() {
freopen("a.out", "w", stdout);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		cout << j*n + (n + i - j) % n + 1 << ' ';
	}
	cout << endl;
}
return 0;
}

Esmė labai paprasta. Jei skirstysim skaičius iš eilės vis kitai grupei, tai gausim kažką tokio:

 1  5  9 13

 2  6 10 14

 3  7 11 15

 4  8 12 16

Kol kas kiekviena grupė turi skirtingas sumas. Kad geriau matytųsi, kaip pasiskirstę dydžiai, iš kiekvieno stulpelio atimsim mažiausią skaičių stulpelyje:

0  0  0  0

1  1  1  1

2  2  2  2

3  3  3  3

Vienodas sumas gausime tuo atvejų, jei kiekviename stulpelyje perstatysim reikšmes taip, kad kiekvienoj eilutėj būtų vien tik skirtingi skaičiai:

0  3  2  1

1  0  3  2

2  1  0  3

3  2  1  0

Prisimuojam ką anksčiau buvom atėmę:

1  8 11 14

2  5 12 15

3  6  9 16

4  7 10 13

Trumpesnis variantas:

 

#include <iostream>

using namespace std;

int main() {
freopen("a.out", "w", stdout);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		cout << j*n + (n + i - j) % n + 1 << ' ';
	}
	cout << endl;
}
return 0;
}

 

Esmė labai paprasta. Jei skirstysim skaičius iš eilės vis kitai grupei, tai gausim kažką tokio:

1 5 9 13

2 6 10 14

3 7 11 15

4 8 12 16

 

Kol kas kiekviena grupė turi skirtingas sumas. Kad geriau matytųsi, kaip pasiskirstę dydžiai, iš kiekvieno stulpelio atimsim mažiausią skaičių stulpelyje:

0 0 0 0

1 1 1 1

2 2 2 2

3 3 3 3

 

Vienodas sumas gausime tuo atvejų, jei kiekviename stulpelyje perstatysim reikšmes taip, kad kiekvienoj eilutėj būtų vien tik skirtingi skaičiai:

0 3 2 1

1 0 3 2

2 1 0 3

3 2 1 0

 

Prisimuojam ką anksčiau buvom atėmę:

1 8 11 14

2 5 12 15

3 6 9 16

4 7 10 13

Geras, man niekaip net nedasunta, kaip sugebejai sugalvoti toki algoritma. Galetum paaiskint kaip apskritai priejai prie tokio paprasto sprendimo?

Geras, man niekaip net nedasunta, kaip sugebejai sugalvoti toki algoritma. Galetum paaiskint kaip apskritai priejai prie tokio paprasto sprendimo?

Sudėtingiausia buvo pastebėt, kad galima skaičius skirstyti grupėms iš eilės, tik reikia vis pakeisti nuo kurio pradedi skirstyti. Pradžioje labiausiai klaidina atvejai, kai N yra lyginis, nes labai lengva sugalvoti būdą, kaip paskirstyti, tačiau šis būdas visiškai netinka nelyginiams variantams.

1 8 11 14

2 5 12 15

3 6 9 16

4 7 10 13

Kadangi ciklai didėja po vieną (kaip ir skaičių skirstymas didėjant po vieną ar paslinkimas per vieną, nuo kurios grupės pradėti skirstyti skaičius stulpelyje), tai tiesiog belieka tinkamai sudėlioti n, i ir j formulę, kad gautum reikiamą rezultatą.

O tos formulės komponentai atitinka tai, praeitame pranešime aiškinau (čia ^[x] yra nuoroda panaudojimui toliau tekste):

(j*n + 1)^[1] + ((n^[2] + i^[3] - j^[4]) % n)^[5]

čia:

• kintamasis i [3] dalina skaičius iš eilės nuo nulio iki n-1 kiekvienam stulpeliui (antra matrica praeitam pranešime);
  
• kintamasis j [4] paslenka elementą, nuo kurio pradedama dalinti, per vieną (paėmus visus skliaustus [5] turėtų išeiti 3 matrica iš praeito pranešimo);
  
• n [2] reikalingas, kad nebūtų imamas modulis iš neigiamo skaičiaus;
  
• skliaustai [1] būtent prideda kiekvieno stulpelio mažiausią reikšmę;
  

Sudėtingiausia buvo pastebėt, kad galima skaičius skirstyti grupėms iš eilės, tik reikia vis pakeisti nuo kurio pradedi skirstyti. Pradžioje labiausiai klaidina atvejai, kai N yra lyginis, nes labai lengva sugalvoti būdą, kaip paskirstyti, tačiau šis būdas visiškai netinka nelyginiams variantams.

 

1  8 11 14

2  5 12 15

3  6  9 16

4  7 10 13

 

Kadangi ciklai didėja po vieną (kaip ir skaičių skirstymas didėjant po vieną ar paslinkimas per vieną, nuo kurios grupės pradėti skirstyti skaičius stulpelyje), tai tiesiog belieka tinkamai sudėlioti n, i ir j formulę, kad gautum reikiamą rezultatą.

 

O tos formulės komponentai atitinka tai, praeitame pranešime aiškinau (čia ^[x] yra nuoroda panaudojimui toliau tekste):

(j*n + 1)^[1] + ((n^[2] + i^[3] - j^[4]) % n)^[5]

čia:

• kintamasis i [3] dalina skaičius iš eilės nuo nulio iki n-1 kiekvienam stulpeliui (antra matrica praeitam pranešime);
  
• kintamasis j [4] paslenka elementą, nuo kurio pradedama dalinti, per vieną (paėmus visus skliaustus [5] turėtų išeiti 3 matrica iš praeito pranešimo);
  
• n [2] reikalingas, kad nebūtų imamas modulis iš neigiamo skaičiaus;
  
• skliaustai [1] būtent prideda kiekvieno stulpelio mažiausią reikšmę;
  

  

Aciu uz paaiskinima, +- dasilo. Na, igyvendinti tokia ideja turbut lengviau, negu apskritai ja sugalvoti. Esi sprendes daug matricu/panasiu uzdaviniu, ar tiesiog kazkas igimto padejo? :D

Aciu uz paaiskinima, +- dasilo. Na, igyvendinti tokia ideja turbut lengviau, negu apskritai ja sugalvoti. Esi sprendes daug matricu/panasiu uzdaviniu, ar tiesiog kazkas igimto padejo? :D

Daug sprendęs