Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Info Coronavirus/Vaccinare vs Fake News

Samsung ue55mu6402 optiuni/setari...

Transmitere Index ENEL

Tradiția impodobirii bradulu...
 R.I.P avocatul31

Plutitor cu temporizator

Lacuit la temperaturi scazute

Network Signal Guru
 Cum se monteaza obiectul asta?

Curent AC produs de alternator

GDPR | Algoritm computer vision p...

Elveția ia in considerare in...
 Windows Defender recuperare

Hackintosh Ryzen 5600g fara placa...

Cum izolez acest fir?

rtorrent - scripting
 

Suma maxima.

* - - - - 1 votes
  • Please log in to reply
32 replies to this topic

#1
Irbaa

Irbaa

    Junior Member

  • Grup: Junior Members
  • Posts: 54
  • Înscris: 15.03.2022
Salut. Am rezolvat o problema insa aparent nu este intocmai rezolvata si nu pot sa imi dau seama unde gresesc.Enuntul problemei suna cam asa:"Se dă o matrice m cu n linii și n coloane. Să se afișeze suma maximă a elementelor situate pe o paralelă la diagonala principală sau secundară."
Ca restrictii avem: "1 ≤ n ≤ 50
    -100 ≤ m[i][j] ≤ 100
    Diagonalele principale și secundare se consideră și ele paralele"

Iar eu am rezolvato in felul urmator :
#include <iostream>
using namespace std;
int main() {
	int n , m[50][50];
	cin >> n;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			cin >> m[i][j];
		}
	}
	int max = -100;
	for(int i = -n + 1; i <= 0; ++i){
		int s = 0;
		for(int j = 1; j <= n + i; ++j){
			s = s + m[j][j - i];
		}
		if (s >= max){
			max = s;
		}
	}
	for(int i = 1; i <= n - 1; ++i){
		int s = 0;
		for(int j = 1; j <= n - i; ++j){
		 s = s + m[j + i][j];
		}
	  
		if(s >= max){
			max = s;
		}
	}
   
  cout << max;
}

Practic trebuie determinata diagonala de suma maxima, nu?Daca da, nu vad unde gresesc.
Ps: Am determinat suma diagonalelor secundare la diagonala principala.

#2
crios339

crios339

    Junior Member

  • Grup: Members
  • Posts: 239
  • Înscris: 27.01.2007
In C/C++ indicii matricilor cred ca pleaca de la 0, nu de la 1.

#3
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 28,245
  • Înscris: 10.08.2005
Ce se intampla daca rotesti matricea principala 45 de grade la stanga sau la dreapta ?

View PostIrbaa, on 04 octombrie 2022 - 13:16, said:

Ps: Am determinat suma diagonalelor secundare la diagonala principala.
pai trebuie sa le vezi pe toate

#4
Lexon

Lexon

    Senior Member

  • Grup: Senior Members
  • Posts: 2,079
  • Înscris: 07.08.2011

Quote

Să se afișeze suma maximă a elementelor situate pe o paralelă la diagonala principală sau secundară.


Adica vrea sa calculezi sumele pe toate paralele si sa afisezi doar suma maxima.

E o matrice patratica cu maxim 50 de elemante pe linie si cu elementele intre -100 si 100,. Deci e despre diagonala si patratica, asa ca nu lucrezi cu ij ci doar cu i, e vorba de diagonale si elementele au forma i,i pt principala sau n-i, i  pt secundara. Paralele au forme asemanatoare.
Diagonalele impart fiecare matricea in doua zone care au forme diferite, deci vei avea patru situatii, deasupra si sub fiecare diagonala. Fiecare zona are cate n-1 diagonale paralele.
Incepi cu care vrei, prima paralela calculata o iei de buna si o inlocuiesti doar daca gasesti alta cu suma mai mare.

Pentru depanare pui sa afiseze elementele pe care le calculeaza.

Edited by Lexon, 04 October 2022 - 16:15.


#5
darkangel2

darkangel2

    Active Member

  • Grup: Members
  • Posts: 1,653
  • Înscris: 26.01.2019
1 Intr-adevar, asa cum a explicat @crios339, in C/C++ indecsii pleaca de la zero; deci daca ai declarat int m[50][50] => indecsii sunt intre 0 si 49. Insa: daca tu ai considerat ca indecsii pleaca de la 1 si ai scris algoritmul corect cf. acestei presupuneri, ar trebui sa functioneze. Singura problema pe care s-ar putea sa o ai este un "Segmentation fault" pentru n=50 deoarece vei incerca sa accesezi memoria nealocata m[i][50] si m[50][j].

2 O matrice n x n are 2n-1 diagonale paralele cu una din diagonale si 2n-1 diagonale paralele cu cealalta => total = 4n-2 sume. Din cate observ, tu calculezi doar 2n-1 sume, deci doar jumatate din numarul necesar de sume.

3 Cand i = - n + 1 si j = 2 => m[j][j - i] = m[ 2 ][ 2 - (- n + 1) ] = m[ 2 ][ 2 + n - 1] = m[ 2 ][ n + 1 ] => incerci sa accesezi coloana (n + 1) care nu exista; probabil ca trebuia sa fie (n - 1)...

#6
darkangel2

darkangel2

    Active Member

  • Grup: Members
  • Posts: 1,653
  • Înscris: 26.01.2019
4 E greu pentru cineva (probabil chiar si pentru tine) sa inteleaga ce fac exact for-urile alea...

#define main_diag_col(diag_id, row) (diag_id + row)
#define main_diag_min_row(diag_id) (diag_id < 0 ? - diag_id : 0)
#define main_diag_max_row(diag_id) (diag_id <= 0 ? n - 1 : n - diag_id - 1)

[ In expresiile de mai sus, fiecare identificator trebuie pus intre paranteze (le-am omis de dragul claritatii), altfel rezultatele nu sunt cele asteptate.... ]

Am numerotat diagonalele paralele cu cea principala astfel:
- diag_id = -(n-1) pentru cea mai indepartata de sub diagonala principala
- diag_id = 0 pentru diagonala principala
- diag_id = +(n-1) pentru cea mai indepartata de deasupra diagonalei principale.

Primul macro intoarce coloana celulei de pe diagonala diag_id si linia row.
Al doilea macro intoarce linia minima de pe diagonala diag_id.
Al treilea marco intoarce linia maxima de pe diagonala diag_id.

Cu aceste 3 macro-uri, codul devine mai usor de inteles:
for (int diag_id = -(n-1); diag_id <= (n-1); diag_id++)
for (int i = main_diag_min_row(diag_id); i <= main_diag_max_row(diag_id); i++)
s += m[ i ][ main_diag_col(diag_id, i) ]

Aceeasi abordare se poate folosi si pentru diagonala secundara, regula acolo fiind ca suma dintre linie si coloana este constanta (pentru o diagonala data).

Edited by darkangel2, 04 October 2022 - 16:35.


#7
Irbaa

Irbaa

    Junior Member

  • Grup: Junior Members
  • Posts: 54
  • Înscris: 15.03.2022
"3 Cand i = - n + 1 si j = 2 => m[j][j - i] = m[ 2 ][ 2 - (- n + 1) ] = m[ 2 ][ 2 + n - 1] = m[ 2 ][ n + 1 ] => incerci sa accesezi coloana (n + 1) care nu exista; probabil ca trebuia sa fie (n - 1)..."
Cand j = 2 , i = -n + 2, fiindca deja trece o data prin al doilea for... sa presupunem ca n = 4 , avem : i = -4 + 1 = -3 .. al doilea for fiind for(int j = 1; j <= n+i ; ++j) avem m[1][1 - (-3)] => m[1][4]. iar n + i = 4 +(-3) = 1. Deci iesim din for si ajungem la primul for unde i = -3 + 1 = -2 , avem m[1][1 + 2] si m[2][2 + 2] iar n + i = 4 - 2 = 2... for ul va rula de exat doua ori.
Multumesc pentru raspunsuri, am sa calculez toate digonalele si am sa revin cu implementarea sau cu vestea ca am reusit sa trec de problema.

#8
darkangel2

darkangel2

    Active Member

  • Grup: Members
  • Posts: 1,653
  • Înscris: 26.01.2019

View PostIrbaa, on 04 octombrie 2022 - 18:38, said:

"3 Cand i = - n + 1 si j = 2 => m[j][j - i] = m[ 2 ][ 2 - (- n + 1) ] = m[ 2 ][ 2 + n - 1] = m[ 2 ][ n + 1 ] => incerci sa accesezi coloana (n + 1) care nu exista; probabil ca trebuia sa fie (n - 1)..."

Ignora asta - n-am vazut ca j <= n + i, deci cand i = - n + 1 => j <= 1 => j nu poate fi 2! :D

#9
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 28,245
  • Înscris: 10.08.2005

View PostIrbaa, on 04 octombrie 2022 - 18:38, said:

Multumesc pentru raspunsuri, am sa calculez toate digonalele si am sa revin cu implementarea sau cu vestea ca am reusit sa trec de problema.
O sa revii cu cod si explicatii de ce ai ales ce ai ales.
Faptul ca treci peste probelama este irelevant daca n-ai invatat nimic.

Edited by MarianG, 05 October 2022 - 07:39.


#10
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 28,245
  • Înscris: 10.08.2005

View Postdarkangel2, on 04 octombrie 2022 - 16:31, said:

[ In expresiile de mai sus, fiecare identificator trebuie pus intre paranteze (le-am omis de dragul claritatii), altfel rezultatele nu sunt cele asteptate.... ]
Tot de dragul claritatii ai putea sa folosesti tag-urile CODE
#define main_diag_col(diag_id, row) (diag_id + row)
#define main_diag_min_row(diag_id) (diag_id < 0 ? - diag_id : 0)
#define main_diag_max_row(diag_id) (diag_id <= 0 ? n - 1 : n - diag_id - 1)


#11
Irbaa

Irbaa

    Junior Member

  • Grup: Junior Members
  • Posts: 54
  • Înscris: 15.03.2022
Se pare ca simpla calculare a sumei elementelor tuturor paralelelor celor doua diagonale nu este bine.

#12
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 28,245
  • Înscris: 10.08.2005
de ce ?

#13
Irbaa

Irbaa

    Junior Member

  • Grup: Junior Members
  • Posts: 54
  • Înscris: 15.03.2022
Fiindca este suficient sa fac suma tuturor paralelelor la una din cele doua diagonale si trebuie sa cuprind toate cazurile in care matricea are elementele nu mai mari decat 100 si nu mai mici decat -100. Se pare ca imi scapa anumite cazuri. Si nu pot sa imi dau seama ce poate exista inafara de cele 3 situatii pe care pe care am testat programul. Situatia in care toate elementele matricii sunt negative, situatia cand toate elementele sunt pozitive si situatia cand elementele sunt si negative si pozitive.

#14
darkangel2

darkangel2

    Active Member

  • Grup: Members
  • Posts: 1,653
  • Înscris: 26.01.2019

View PostIrbaa, on 06 octombrie 2022 - 13:32, said:

Situatia in care toate elementele matricii sunt negative, situatia cand toate elementele sunt pozitive si situatia cand elementele sunt si negative si pozitive.

Ai prezentat 3 situatii.
In ce fel sunt diferite aceste situatii din punct de vedere al operatiei de adunare algebrica?
De exemplu: care este diferenta (din punct de vedere al algoritmului), intre adunarea numerelor 1 + 2 si adunarea numerelor (-1) + (-2)? Nu este tot o adunare?

#15
Irbaa

Irbaa

    Junior Member

  • Grup: Junior Members
  • Posts: 54
  • Înscris: 15.03.2022
Poi, aceste 3 situatii inglobeaza suma posibilitatilor pe care eu le vad in aceasta problema si anume : a + b , -a + (-b) si -a + b.

#16
darkangel2

darkangel2

    Active Member

  • Grup: Members
  • Posts: 1,653
  • Înscris: 26.01.2019

View PostIrbaa, on 06 octombrie 2022 - 14:43, said:

a + b , -a + (-b) si -a + b

Toate aceste 3 situatii sunt, de fapt, una singura: a + b.
Eu zic ca rezultatul a + b este corect indiferent daca: a si b sunt pozitive, negative, unul negativ si altul pozitiv, mai mari decat 15, mai mici decat 3, pare, impare, multiplii de 13 etc.
Este o singura situatie, nu sunt mai multe...

Edited by darkangel2, 06 October 2022 - 14:55.


#17
Irbaa

Irbaa

    Junior Member

  • Grup: Junior Members
  • Posts: 54
  • Înscris: 15.03.2022
Ok, rectific... Am identificat o singura situatie de care am nevoie sa rezolv problema asta si nu vad altele inafara de asta.

Edited by Irbaa, 06 October 2022 - 15:20.


#18
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 28,245
  • Înscris: 10.08.2005
Irbaa câte sume (diagonale paralele) are o matrice?

Anunturi

Second Opinion Second Opinion

Folosind serviciul second opinion ne puteți trimite RMN-uri, CT -uri, angiografii, fișiere .pdf, documente medicale.

Astfel vă vom putea da o opinie neurochirurgicală, fără ca aceasta să poată înlocui un consult de specialitate. Răspunsurile vor fi date prin e-mail în cel mai scurt timp posibil (de obicei în mai putin de 24 de ore, dar nu mai mult de 48 de ore). Second opinion – Neurohope este un serviciu gratuit.

www.neurohope.ro

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate