👤
a fost răspuns

Pentru multimea de numere {x1, x2, x3, x4, ..., xN} (N>=3) multimea sumelor de perechi este
{x1+x2, x1+x3, x1+x4, x2+x3,x2+x4,x3+x4, ...,}. (s_k = x_i + x_j, i != j). Se da multimea sumelor
de perechi si se cere gasirea multimii initiale. Multimea sumelor de perechi se da intr-o ordine
oarecare.
Intrare
6 105 11 101 110 15
Ieșire
1 5 10 100

Răspuns :

Răspuns:

#include <iostream>

#include <fstream>

#include <algorithm>

using namespace std;

ifstream f("sumeperechi.in");

ofstream g("sumeperechi.out");

int n, a[1000], v[500], sum;

int main()

{

   while (f >> sum)

   {

       a[++n]=sum;

   }

   sort(a+1, a+n+1);

   

   int i=3, k=2, p=1;

   while (i<=n)

   {

       ++k;

       v[k]=(a[i]+a[i-1]-a[p])/2;

       p=i; i=i+k;

   }

   v[1]=a[2]-v[3]; v[2]=a[1]-v[1];

   for (i=1; i<=k; ++i)

       g << v[i] << " ";

}

Explicație:

explicaţia e cam dificilă... am mers pe cărări întortochiate până am ajuns la asta. Din start am înţeles că trebuie de sortat crescător sumele date, pe care le-am plasat într-un vector a[] . După, mi-a venit ideea să le plasez, din vectorul sortat, într-o matrice indexată de la 1 la m, deasupra diagonalei principale. Primul element în x[1][2], parcă r fi x1+x2, după completez coloanele de sus în jos şi de la stânga la dreapta până la diagonala principală şi indicii matricei ne sugerează ce sume se pun în ea. în x[1][3] suma x1+x3 şamd. Aici apărea problema care este cardinalul multimii căutate, adică m. Se poate calcula matematic ca Combinări din m câte 2 este egal cu n, numărul de sume introduse. Se obţine m*(m-1)=2*n şi cu un ciclu se poate găsi m. Dacă vei plasa într+o matrice sumele 6 7 9 10 12 13 13  

 14 16 19 care sunt sumele pentru vectorul (căutat) 2 4 5 8 11, atunci cred că vei înţelege logica următoarei secvenţe care determină vectorul căutat.

for (j=2; j<=m; ++j)

{ for (i=1; i<j; ++i) x[i][j]=a[p++]; }, astfel am plasat sumele in matrice

Acum urmeaza gasirea vectorului cautat dupsumele plasate in matrice

for (i=2; i<m; ++i)

{for (j=3; j<=m; ++j) v[j]=(x[i][j+x[i-1][j]-x[i-1][j-1])/2; }

v[1]=x[1][3]-v[3]; v[2]=x[1][2]-v[1];

Dupa m-am dezis de matrice, ca sa nu mai aflu m, si am realizat varianta postata la care matricea mi-a sugerat ideea

Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Nu ezitați să ne contactați pentru orice întrebare sau dacă aveți nevoie de asistență suplimentară. Vă așteptăm cu drag data viitoare și nu uitați să ne adăugați la favorite!


ID Learners: Alte intrebari