Wyszukiwanie ilosci kombinacji spelniajacych rownianie.

0

Dany jest zbiór A nie większy niż 100 elementów. Odnaleźć ilość kombinacji spełniających równanie (x*y+z)/k - e = q; gdzie każda liczba należy do A. Przykład: A={5, 7, 10}, liczba kombinacji: 10. Dziękuję za wszelką pomoc.

0

Proste to zadanie. Przypisz zmienne do indeksów. Utwórz dwie tablice: jedną na wartości zmiennych, drugą wskazującą na element zbioru A dla każdej zmiennej. Zwiększaj indeksy w tej drugiej tablicy i sprawdzaj.

/* (x*y+z)/k - e = q */
/* przekształcamy do "bezpiecznej" postaci: (x*y)+z=k*(q+e) */

double %A[]={5,7,10} /* zbiór liczb */
#define IloscLiczb sizeof...(A) /*(sizeof(A)/sizeof(A[0]))*/

/* w równaniu mamy 6 różnych zmiennych */
#define VARCOUNT 6

double zmienna[VARCOUNT]
int pos[VARCOUNT] /* wyzerowane */
int kombinacje

try /* na potrzeby przerwania pętli */
	while (1)
		/* przypisujemy wartości zmiennym */
		for (int i=0; i<VARCOUNT; i++)
			zmienna[i] = A[pos[i]]
		next i

		/* umówmy się na następujące indeksy zmiennych: */
		enum indeksy_zmiennych
			x=0, y=1, z=2, k=3, q=4, e=5
		endenum

		/* sprawdzamy kombinację, oraz czy k nie jest zerem */
		if ((zmienna[x]*zmienna[y])+zmienna[z]==zmienna[k]*(zmienna[q]+zmienna[e]) && zmienna[k])
			kombinacje++

			declare import, printf(...)

#if typeof(zmienna)==@TYPEFLOAT

			printf("%2d: (%f*%f)+%f=%f*(%f+%f)\n", kombinacje,double(zmienna[x]),\
				double(zmienna[y]),double(zmienna[z]),double(zmienna[k]),\
				double(zmienna[q]),double(zmienna[e]))

#elif typeof(zmienna)==@TYPEDOUBLE

			printf("%2d: (%f*%f)+%f=%f*(%f+%f)\n", kombinacje,zmienna[x],zmienna[y],\
				zmienna[z],zmienna[k],zmienna[q],zmienna[e])
#else
			printf("%2d: (%d*%d)+%d=%d*(%d+%d)\n", kombinacje,zmienna[x],zmienna[y],\
				zmienna[z],zmienna[k],zmienna[q],zmienna[e])
#endif /*TODO double80 int64 int128*/
		endif

		/* następna kombinacja */
		for (i=0; i<=VARCOUNT; i++)
			if (i==VARCOUNT)
				throw "nie ma więcej kombinacji" /* wyskakuje poza endtry*/
			endif
			/* zwiększaj pos[0] póki nie przekracza ilości elementów A */
			/* jeśli nie przekracza to przerwij pętlę. */
			/* else wyzeruj pos[0] i zwiększ pos[1] ...*/
			if (++pos[i] >= IloscLiczb)
				pos[i] = 0
				/* ++pos[i+1] w następnym przebiegu */
			else
				break
			endif
		next i
	endwhile
endtry

printf("\nznaleziono %d kombinacj%s\n", kombinacje, kombinacje==0?"i":kombinacje>4?"i":"e")

0

Tak, nie chodziło mi o bruta. Napisałem coś takiego:

#include <cstdio>
#include <vector>
#include <algorithm>
#define lli long long int

// ---------------------------   GLOBALS  --------------------------- //
int n, tab[100];
std::vector<int>L;
std::vector<int>R;

// ---------------------------  FUNCTIONS --------------------------- //
inline void PREPARE();
lli COUNT();

// ---------------------------    MAIN    --------------------------- //
int main()
{
    PREPARE();	
    printf("%lld\n", COUNT());
}

// ---------------------------  FUNCTIONS --------------------------- //
inline void PREPARE()
{
	scanf("%d", &n);
	for(int i=0; i<n; i++)
		scanf("%d", &tab[i]);
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			for(int k=0; k<n; k++)
			{
				L.push_back(tab[i]*tab[j]+tab[k]);
				if(tab[i]!=0)
					R.push_back(tab[i]*(tab[j]+tab[k]));
			}
	std::sort(L.begin(), L.end());
	std::sort(R.begin(), R.end());
}
lli COUNT()
{
	lli retr=0;
	for(std::vector<int>::iterator it=L.begin(); it!=L.end(); it++)
		retr-=std::lower_bound(R.begin(), R.end(), *it)-std::upper_bound(R.begin(), R.end(), *it);
	return retr;
}

2

Fajny pomysł, ale liczenie można jeszcze poprawić (upper_bount jest zbędnym narzutem wyszukiwania).

for(std::vector<int>::iterator it=L.begin(); it!=L.end(); it++) {
    std::vector<int>::iterator b = std::lower_bound(R.begin(), R.end(), *it);
    while (b!=R.end() && *b==*it) {
        ++b;
        ++retr;
    }
}

poza tym warto dodać L.reserve(nnn); i R.reserve(nnn) powinno to zapobiec niepotrzebnym realokacjom wektorów.

0

Wow, dzięki wielkie, przyspieszyło średnio o 0.11 sekundy :) Super!

0

Przetestuj to rozwiązanie, powinno być zdecydowanie szybsze (i napisz jak wyszło, żeby przekonać Marka):

#include <cstdio>
#include <vector>
#include <algorithm>
#include <tr1/unordered_map>
using std::tr1::unordered_map;
#define lli long long int

// ---------------------------   GLOBALS  --------------------------- //
int n, tab[200];
unordered_map<int,long long>L;
unordered_map<int,long long>R;

// ---------------------------  FUNCTIONS --------------------------- //
inline void PREPARE();
lli COUNT();

// ---------------------------    MAIN    --------------------------- //
int main()
{
    PREPARE();
    printf("%lld\n", COUNT());
}
// ---------------------------  FUNCTIONS --------------------------- //
inline void PREPARE()
{
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d", &tab[i]);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            for(int k=0; k<n; k++)
            {
                L[tab[i]*tab[j]+tab[k]]+=1;
                if (tab[i]!=0)
                    R[tab[i]*(tab[j]+tab[k])]+=1;
            }
}
lli COUNT()
{
    lli retr=0;
    for(unordered_map<int,long long>::iterator it=L.begin(); it!=L.end(); it++)
        retr+=it->second*R[it->first];
    return retr;
}