Sfidë për të gjetur kufizat natyrore të një shume

[Borix]

Pershendetje,

Te zhvillohet nje program (ose minimalisht nje algoritem formal) qe, kur jepet nje numer n, te gjeje te gjithe numrat (natyrore) m1, m2, ...., m_k te tille qe

m1 + m2 + .... + m_k = n

dhe

1/m1 + 1/m2 + ... + 1/m_k = 1.

Kjo probleme u eshte propozuar studenteve te matematikes nga John Nash, por per te bere proven matematikore qe cdo numer natyror n>32 mund te paraqitet ne ate forme. Ne rastin tone, programi duhet te funksionoje per n>=1 (pra, duhet te jete i pergjithshem). Zgjidhja kompjuterike nuk eshte e thjeshte, por as shume e veshtire. Gjuhet e lejuara: C/C++. (Pascal-it iu bene te dyzetat pak kohe me pare). Zgjidhjen time do ta paraqes pasi te jete nxitur diskutimi...

[xfiles]

...
Gjuhet e lejuara: C/C++. (Pascal-it iu bene te dyzetat pak kohe me pare). ...

e pse mos te perfshihen Java,PHP,Pascal,ASM,Delphi,VB,C#,python etj etj?

[Ardi_Pg_ID]

Cfare roli ka varjabli m ne kete pike sqaroje me shume problemin.
Zgjidhja kompjuterike eshte shume e veshtire ... sma mer mendja :P

[Borix]

e pse mos te perfshihen Java,PHP,Pascal,ASM,Delphi,VB,C#,python etj etj?

Perdor edhe machine lang po te duash - ajo ishte sa per te mbushur postimin me llafe...

Cfare roli ka varjabli m ne kete pike sqaroje me shume problemin.

Problemi eshte mjaftueshmerisht i qarte. m_i eshte nje numer natyror dhe shuma e m_i per te gjithe i (nga 1 deri ne k) jep numrin natyror n. Pershembull, per n=4, kemi si zgjidhje m1=2 dhe m2=2, sepse 2+2=4 dhe 1/2 + 1/2 = 1.

Zgjidhja kompjuterike eshte shume e veshtire ... sma mer mendja :P

Me beso, zgjidhja eshte e veshtire. Per gjetjen e nje algoritmi precis dhe per programimin (qe ka ca klecka) e ketij problemi me eshte dashur nje perpjekje e konsiderueshme tre-ditore. Kjo probleme me eshte dhene ne fillim fare nga F. Alimadhi, qe tani punon ne Harvard University.

... - Albert Einstain

... - Albert Einstein!

[Borix]

Hints:
* Nje numer i dhene n, mund te kete nje ose me shume perfaqesime kufizash.
Psh. n = 22 ka keto perfaqesime:
2 4 8 8
2 5 5 10
3 3 4 12.

* Kufizat nuk duhet te perseriten. Pra nese programi juaj gjen zgjidhjen 2 4 8 8, atehere 8 8 4 2 quhet perseritje. (Pra, ne cilen gjendje te vektorit duhet te ndaloje kerkimi i programit tuaj?).

[Borix]

U shkri diskutimi ne kete teme. Po paraqes zgjidhjen pa ndonje raport shpjegimi...

/*
	Program:	Find all numbers n>=1, where
						
			    n = m_1 + m_2 + ... + m_k, such that

			     1       1               1 
			    ---  + --- + ... +  --- = 1.
			    m_1    m_2          m_k 

  Programmer:		*Borix*
  Date:                 10/15/2005

*/

#include 
#include 
#define N 200

FILE *fout;

int main (void)
{
	double sum=0.0;
	int n, i, k, l, s=0, done, v[N];

	fout=fopen("result.txt","a");

	/* testo 76 numrat e pare: */
	for (n=1; n<=76; n++) {
		fprintf(fout,"%d:\n",n);

		/* Kufizat fillestare: */
		for (i=0;iwhile (!done){

			s=0;
			for (i=0;iif (i>=l)
					v[i]=v[l];
				s+=v[i];
			}
			
			if (s>n+2) done=1;
			
			l=k-2; // indeksi per el. e parafundit te zones se testimit aktual

			// elementi i fundit += [shuma - numrin e dhene]:
			if (selse if (s>n) {
				v[i-1]-=s-n;
			}
			
			sum=0.0;
			for (i=0;idouble)(v[i]);

			// ose sum==1.0, por per disa arsye:
			if (sum>=0.9999999999 && sum<=1.0000000001 && v[k-1]>=v[k-2]){
				fprintf(fout,"   ");
				for (i=0;i// rrit elementin e parafundit me 1


			/* nese elementi i parafundit (dhe para inkrementimit)
			 eshte me i madh ose baraz me elementin e fundit
			 atehere mbaron kerkimi ne ate pike. 
			*/
			if (v[l]-1>=v[l+1]) {

				l=k-2;
				while (v[l]>=v[k-1]){
					--l;
				}
				
				if (l>=0 && v[l]+1<=v[l+1]) ++v[l];
				
			}
			
			// zgjero hapesiren e kerkimit:
			if (l==-1){
				++k; l=0;
				while (l//end while not done

		fprintf(fout,"\n\n");

	}//end for n
	
	fclose(fout);

	return 0;
}

[edspace]

Borix,

Unë isha duke punuar për zgjidhjen, por koha ka qënë e kufizuar. I kam dhënë një zgjidhje problemit por duhet t'i bëj ca pastrime dhe do e hedh nesër.

[Borix]

Ok, bukur. Eshte mire kur ke me shume se nje zgjidhje, me ka thene nje profesor i Pace University, sepse rrit bagazhin e teknikave te te menduarit...

[edspace]

Po hedh më poshtë zgjidhjen time të sfidës në gjuhën C++.

Algoritmi i gjen kufizat me anë të një funksion ripërsëritës/rekursiv (recursive) që provon kombinacione të ndryshme të kufizave dhe zgjedh ata që plotësojnë kushtet e problemës.

Për të bërë algoritmin sa më të shpejtë, shuma e kufizave dhe shuma e të anasjelltave të kufizave llogaritet vetëm njëherë për çdo bashkësi unike kufizash . Shumat kalohen në çdo cikël të algoritmit bashkë me listën e kufizave dhe një kufizë të re të mundshme.

S'kam pasur shumë kohë për ta testuar plotësisht algoritmin, por rezultatet janë të njëjtë me programin e Borix më lart. Kontrollova disa rezultate me dorë dhe ishin të saktë.

Mirëpres sugjerimet, korrigjimet, pyetjet.


sfide.cpp - main dhe algoritmi qe gjen kufizat

//
// Ky program gjen kufizat natyrore [m_1, m_2, ..., m_k], shuma e të cilave është
// n >= 1 dhe shuma e të anasjelltave është 1.
//
//          n = m_1 + m_2 + ... + m_k
//
//            dhe
//
//           1       1           1
//          ---  + --- + ... +  --- = 1
//          m_1    m_2          m_k
//
//
//   Autor:     Eduard Papa  (edspace ET comcast PIKE net)
//   Data:     18/04/2007
//   Perpilues:   g++ 3.4.2
//

#include <iostream>
#include <list>
#include "thyese.h"

#define ndaj ,
#define uint unsigned int

using namespace std;

void printoListen(list<uint> & kufizat) {
  for (list<uint>::iterator it = kufizat.begin(); it != kufizat.end(); it++) {
    cout << *it << " ";
  }
  cout << endl;
}

void zbertheShumen(uint nisje,
           uint shumaCastit,
           uint shuma,
           Thyese<uint> & shumaThyesave,
           list<uint> & kufizat) {

  kufizat.push_back(nisje);
  Thyese<uint> shumaEReEThyesave = shumaThyesave + Thyese<uint>(1 ndaj nisje);
  Thyese<uint>::thjeshto(shumaEReEThyesave);
  
  if (shumaCastit == shuma) {
    if(shumaEReEThyesave.eshteNje()) {
      printoListen(kufizat);
    }
    kufizat.pop_back();
    return;
  }
  
  if(shumaEReEThyesave.eshteMeEMadheSeNje()) {
    kufizat.pop_back();
    return;
  }

  for (int i = nisje; i + shumaCastit <= shuma; i++) {
    zbertheShumen(i, shumaCastit + i, shuma, shumaEReEThyesave, kufizat);
  }

  kufizat.pop_back();
}


void zbertheShumen(uint shuma) {
  Thyese<uint> zero(0 ndaj 1);
  list<uint> kufizat;

  for (int i = 1; i <= shuma; i++) {
    zbertheShumen(i, i, shuma, zero, kufizat);
  }
}


int main(int argc, char *argv[]) {

  uint shuma;

  while (shuma != 0) {
    cout << "Shuma: ";
    cin >> shuma;
    zbertheShumen(shuma);
  }

    cin.get();
    return EXIT_SUCCESS;
} 

thyese.h - klasë ndihmëse që përfaqëson thyesat.

//
//   Thyese eshte nje klase shabllon qe prezanton nje numer ne forme thyese, 
//   si për shembull: 1/2, -3/4, 1.5/5.1, A1/A2. Emeruesi dhe numeruesi duhet 
//   te jene te te njejtit tip.
//
//   Shembull:
//       #define ndaj ,
//    Thyese<unsigned int> a(1 ndaj 2);
//    Thyese<unsigned int> b(1 ndaj 3);
//    Thyese<int> c = a + b;
//    cout << c << endl;
//
//   Autor:     Eduard Papa (edspace ET comcast PIKE net)
//   Data:     18/04/2007
//


#ifndef _THYESE_EPAPA_20070414_
#define _THYESE_EPAPA_20070414_

#include <iostream>

using namespace std;

template<class T>
class Thyese {
  private:
    T _numeruesi;
    T _emeruesi;

  public:
    Thyese() {}

    Thyese(T numeruesi, T emeruesi)
        : _numeruesi(numeruesi), _emeruesi(emeruesi) {}

    T merrNumeruesi() const {
      return _numeruesi;
    }
    
    T merrEmeruesi() const {
      return _emeruesi;
    }
    
    void verNumeruesi(T numeruesi) {
      _numeruesi = numeruesi;
    }
    void verEmeruesi(T emeruesi) {
      _emeruesi = emeruesi;
    }

    bool eshteNje () {
      return (this->merrNumeruesi() == this->merrEmeruesi());
    }
    
    bool eshteMeEMadheSeNje () {
      return (this->merrNumeruesi() > this->merrEmeruesi());
    }

    // Thjeshton thyesen duke perdorur algoritmin Euklidian
    static void thjeshto (Thyese<unsigned int> & thyesa) {
         unsigned int x = thyesa.merrNumeruesi();
      unsigned int y = thyesa.merrEmeruesi();

      if (x < y)
      {
        unsigned int tmp = x;
        x = y;
        y = tmp;
      }
      
      unsigned int mbetja;
      while (y != 0) {
        mbetja = x % y;
        x = y;
        y = mbetja;
      }
      
      thyesa.verNumeruesi(thyesa.merrNumeruesi() / x);
      thyesa.verEmeruesi(thyesa.merrEmeruesi() / x);
    }
    
    template<class TT>
    friend Thyese operator+(const Thyese & a, const Thyese & b);
    
    template<class TT>
    friend ostream & operator<<(ostream & out, const Thyese & b);
};

template<class T>
Thyese<T> operator+(const Thyese<T> & a, const Thyese<T> & b) {
  Thyese<T> shuma ;
  shuma.verNumeruesi(a.merrNumeruesi() * b.merrEmeruesi()
             + b.merrNumeruesi() * a.merrEmeruesi());
  shuma.verEmeruesi(a.merrEmeruesi() * b.merrEmeruesi());
  return shuma;
}

template<class T>
ostream & operator<<(ostream & out, const Thyese<T> & th) {
  out << th.merrNumeruesi() << "/" << th.merrEmeruesi();
}

#endif 

Ja disa rezultate të programit. Shtypni 0 për të dalë nga programi.

Shuma: 1
1
Shuma: 2
Shuma: 3
Shuma: 4
2 2
Shuma: 5
Shuma: 6
Shuma: 7
Shuma: 8
Shuma: 9
3 3 3
Shuma: 12
Shuma: 15
Shuma: 16
4 4 4 4
Shuma: 17
3 4 4 6
Shuma: 18
3 3 6 6
Shuma: 22
2 4 8 8
2 5 5 10
3 3 4 12
Shuma: 33
3 3 9 9 9
3 5 5 5 15
Shuma: 51
3 3 5 10 30
4 4 4 9 12 18
4 4 5 6 12 20
6 6 6 6 9 9 9
Shuma: 64
2 4 8 10 40
2 5 9 15 15 18
2 5 10 12 15 20
2 6 7 14 14 21
2 6 8 12 12 24
2 7 7 9 18 21
3 3 4 18 36
3 4 5 8 20 24
3 4 5 10 12 30
3 5 5 6 15 30
3 6 6 10 12 12 15
3 6 8 8 9 12 18
4 4 6 10 10 15 15
4 4 7 7 14 14 14
4 4 8 8 8 16 16
4 4 8 8 10 10 20
4 5 5 8 10 16 16
4 5 5 10 10 10 20
4 5 7 7 7 14 20
4 6 6 8 8 8 24
5 5 6 6 8 10 24
8 8 8 8 8 8 8 8
Shuma: 70
2 4 16 16 16 16
2 6 6 14 21 21
2 6 6 16 16 24
3 3 8 8 24 24
3 4 9 12 12 12 18
3 5 6 12 12 12 20
3 5 8 10 10 10 24
3 6 6 6 7 42
3 7 7 7 8 14 24
4 4 4 8 10 40
4 4 5 9 15 15 18
4 4 5 10 12 15 20
4 4 6 7 14 14 21
4 4 6 8 12 12 24
4 4 7 7 9 18 21
4 5 5 6 15 15 20
4 5 5 8 8 20 20
4 5 6 7 7 20 21
4 8 8 10 10 10 10 10
4 9 9 9 9 9 9 12
5 5 5 5 10 20 20
5 5 10 10 10 10 10 10
5 7 7 7 10 10 10 14
6 6 6 8 8 12 12 12
6 6 6 9 9 9 10 15
7 7 7 7 7 7 14 14
Shuma: 101
2 3 24 24 24 24
2 4 5 30 60
2 5 10 15 20 21 28
2 5 10 18 18 18 30
2 5 12 12 20 20 30
2 5 14 15 15 15 35
2 6 6 12 15 60
2 6 8 12 21 24 28
2 6 9 11 18 22 33
2 6 9 12 18 18 36
2 7 7 14 15 21 35
2 7 10 10 15 15 42
2 9 10 10 10 15 45
2 12 12 15 15 15 15 15
3 3 10 10 15 30 30
3 3 10 14 14 15 42
3 4 4 9 27 54
3 4 4 10 20 60
3 4 5 10 21 28 30
3 4 6 8 16 32 32
3 4 6 8 20 20 40
3 4 6 11 11 22 44
3 4 6 12 12 16 48
3 4 8 16 16 18 18 18
3 4 9 12 15 18 20 20
3 4 10 10 18 18 18 20
3 4 10 12 12 20 20 20
3 4 12 12 14 14 14 28
3 5 6 6 18 18 45
3 5 6 7 10 35 35
3 5 6 10 11 11 55
3 5 6 12 15 20 20 20
3 5 7 12 12 14 20 28
3 5 10 10 12 12 14 35
3 6 6 8 18 18 18 24
3 6 6 10 12 15 21 28
3 6 6 12 12 12 20 30
3 6 7 7 8 14 56
3 6 8 8 9 18 21 28
3 6 8 8 12 14 15 35
3 6 8 10 10 10 24 30
3 8 8 8 8 11 22 33
3 8 8 8 8 12 18 36
3 8 8 8 10 12 12 40
3 10 10 12 12 12 12 15 15
4 4 4 8 9 72
4 4 4 9 15 20 45
4 4 4 10 15 16 48
4 4 5 12 14 20 21 21
4 4 5 12 16 16 20 24
4 4 6 6 9 36 36
4 4 6 8 15 20 20 24
4 4 6 9 12 18 24 24
4 4 6 9 15 15 18 30
4 4 6 10 12 15 20 30
4 4 7 8 12 14 24 28
4 4 8 8 9 18 20 30
4 4 9 9 9 11 22 33
4 4 9 9 9 12 18 36
4 5 5 9 9 9 60
4 5 5 9 10 18 20 30
4 5 6 6 10 10 60
4 5 6 6 12 20 24 24
4 5 6 6 15 15 20 30
4 5 6 8 8 20 20 30
4 5 6 9 9 12 20 36
4 5 10 10 12 15 15 15 15
4 5 12 12 12 12 12 12 20
4 6 6 6 10 14 20 35
4 6 6 6 10 15 18 36
4 6 6 7 7 20 21 30
4 6 6 7 12 12 12 42
4 6 6 8 9 10 18 40
4 6 8 8 15 15 15 15 15
4 6 8 9 12 12 16 16 18
4 6 9 9 9 16 16 16 16
4 6 9 9 10 12 15 18 18
4 6 9 10 10 12 12 18 20
4 7 7 10 10 12 15 15 21
4 7 8 8 10 14 14 15 21
4 8 8 8 8 15 15 15 20
4 8 8 8 10 12 12 15 24
4 8 8 9 9 9 18 18 18
5 5 5 6 10 20 20 30
5 5 6 10 15 15 15 15 15
5 5 7 10 10 14 14 15 21
5 5 8 8 10 15 15 15 20
5 5 8 10 10 12 12 15 24
5 5 9 9 9 10 18 18 18
5 5 9 9 9 12 12 20 20
5 6 6 6 8 10 20 40
5 6 6 6 9 12 12 45
5 6 6 8 12 12 16 16 20
5 6 6 9 9 15 15 18 18
5 6 6 9 10 12 15 18 20
5 6 6 10 10 10 18 18 18
5 6 6 10 10 12 12 20 20
5 6 7 7 10 15 15 15 21
5 6 8 8 8 12 15 15 24
5 6 8 8 9 9 18 18 20
5 6 10 10 10 10 10 10 30
5 7 7 8 8 10 15 20 21
5 8 8 8 8 8 12 20 24
5 8 8 8 8 10 12 12 30
6 6 6 6 12 15 15 15 20
6 6 6 6 14 14 14 14 21
6 6 6 7 9 14 14 18 21
6 6 6 8 8 12 15 20 20
6 6 6 8 9 12 12 18 24
6 6 6 9 9 9 14 21 21
6 6 6 9 9 9 16 16 24
6 6 7 7 7 14 18 18 18
6 6 7 7 9 9 18 18 21
6 6 7 8 8 12 12 14 28
6 7 7 7 7 10 15 21 21
6 7 7 7 10 10 10 14 30
6 7 7 8 8 8 12 21 24
9 9 9 10 10 10 10 10 12 12
Shuma: 0

Shkarkoni kodin: Sfida_kodi.zip

[Borix]

Edspace, zgjidhja rekursive eshte elegante. Rezultatet jane te njejte me ato qe kam une, per sa kohe qe kemi rezultatet e sakta .

Mund te funksionoje modifiki i meposhtme:

    for (int i = 2; i <= shuma/2; i++)

Kjo mund ta ule hapesiren e kerkimit (rasti i n=1 perjashtohet, por mund te modifikohet qe te shtohet ne nje nga if-et e rekursionit).