Mam powiedzmy liczby {x1,x2,x3} i dla liczby n=2 chcę uzyskać x1x2 + x1x3 + x2*x3. Analogicznie dla większej ilości liczb i innych n. Jak takie coś zrobić? Napisałem jakieś tam dwie pętle, ale zorientowałem się, że to działa tylko dla n=2.
Pytanko uściślające. Dla {x1,x2,x3} i n=3 chcesz uzyskać x1x2x3?, a dla n=4 chcesz uzyskać 0?
Dla n=3 - zgadza się. Dla n=4 nie rozpatrujemy, z góry zakładamy, że maksymalna wartość n jest równa ilości podanych liczb. Chyba, że to coś uprości, to może być 0 dla n=4.
powiedzmy, że iksów jest m (ile może ich być, >64?)
składników sumy ma być tyle ile ile kombinacji n elementowych ze zbioru m?
Jeżeli o to właśnie chodzi, możesz kombinować ze wzorami Viete'a (to według mnie). Będzie trzeba wtedy policzyć współczynniki równania - będzie miało to złożoność kwadratową (uważam, że to jest dość nieźle). W tym przypadku martwi mnie wielkość liczb, bo dla powiedzmy 200 liczb od -1000 do 1000 będziesz operował na liczbach rzędu 10600, a to daleeeeeeko poza standardowymi strukturami :D
Xitami, zgadza się.
Nie będę w tym korzystać z żadnych wielkich liczb, ilość liczb też nie będzie jakaś szczególnie duża, wszystko będzie się mieścić w zakresie do 10.
Próbowałem coś takiego zrobić, ale źle działa:
[code]
SumIlo[l_, n_] := Module[{a, b, i = 0, j, k, s = 0, r},
b = Length[l];
a = SymbNew[Length[l], n];
While[i < a,
For[j = 1, j <= b, j++,
r = l[j];
k = j + 1;
While[k <= n,
i = i + 1;
r = r*l[k];
k = k + 1;
];
s = s + r;
];
];
s
];
[/code]
(Kod z Mathematiki)
SymbNew to funkcja obliczająca symbol Newtona, Length[l] to długość tablicy/listy l, Modulo to słowo kluczowe rozpoczynające funkcję, zmienne po "Modulo" w nawiasach {} to zmienne lokalne, l_, n_ oznacza, że to argumenty funkcji SumIlo.
Da się to jakoś poprawić, żeby było ok?
Nie wiem czy o to chodziło, bo w między czasie się pogubiłem. Natomiast Mathematici nie znam i ciężko mi analizować ten kod (tzn. nie chce mi się :P).
Jeśli dobrze rozumiem to:
gdy n=1 => X1 => nic nie mnożymy => sum = 0;
gdy n=2 => x1, x2 => sum = x1x2
gdy n=3 => x1,x2,x3 => sum = x1x2+x1x3+x2x3
gdy n=4 => x1,x2,x3,x4 => sum = x1x2+x1x3+x1x4+x2x3+x2x4+x3x4
itd.
to ja bym to zrobił tak:
int i, j;
const int n; //twoja wartość x-ów
double wartosci[n];
... //tu inicjujesz jakieś wartości w tej tablicy etc.
double sum = 0.0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
sum += wartosc[i]*wartosc[j];
}
ten kod był robiony na bardzo szybko i chyba ma kilka błędów ale już sobie chyba poradzisz :)
#include <stdio.h>
typedef unsigned int ulong;
ulong next(ulong x) {
ulong r = x & -x;
x += r;
if ( 0==x ) return 0;
ulong z = x & -x;
z -= r;
while ( 0==(z&1) ) { z >>= 1; }
return x | (z>>1);
}
int main(){
int n=2, m=4, k;
k=scanf("%d %d", &m, &n);
ulong x=(1<<n)-1;
ulong y=next(x<<(m-n));
ulong z;
while(x!=y){
z=x; k=0;
printf("\n+");
while(z){
if(z&1)
printf(" X%d",k);
z>>=1; k++;
}
x=next(x);
}
return 0;
}
Dzięki wielkie za pomoc :)
to samo, ale nie tak samo
// kombinacje
#include <stdio.h>
void printc(int comb[], int k) {
int i;
for (i = 0; i < k; ++i)
printf("%d ", comb[i]+1);
printf("\n");
}
float prod(int comb[], int k, float x[]){
float p=1; int i;
for(i=0; i<k; i++)
p*=x[comb[i]];
return p;
}
int next_comb(int comb[], int k, int n) {
int i = k - 1;
++comb[i];
while ((i >= 0) && (comb[i] >= n - k + 1 + i)) {
--i;
++comb[i];
}
if (comb[0] > n - k)
return 0;
for (i = i + 1; i < k; ++i)
comb[i] = comb[i - 1] + 1;
return 1;
}
int main(int argc, char *argv[]) {
int n = 5, k = 3, comb[69]; //comb[k+1]
int i;
for (i = 0; i < k; ++i) comb[i] = i;
float sum=0, x[69]; // x[n]
for(i=0;i<n;i++)
x[i]=i+1; // ?????
printc(comb, k);
sum=prod(comb, k, x);
while (next_comb(comb, k, n)){
printc(comb, k);
sum+= prod(comb, k, x);
}
printf("%f\n", sum);
return 0;
}
Xitami, może to głupie pytanie, ale jaki jest cel działania twojego programu? bo trochę się w nim gubię :/
Wiesz? Ja też jestem ciekawy.
Ciekawe czy to tylko zabawa w kombinacje, czy też ma to jakiś głębszy sens?
Może _Mithrandir coś powie.
Xitami, jak zawsze przekombinowałeś, twoje dzieło przy wprowadzeniu 2 4 wypisuje chyba dla 4 32.
No i strasznie nakombinowałeś, oczywiście pomijając fakt że twoja metoda ma ograniczenia m<=64;
#include <iostream>
using namespace std;
//#define ONBIT
#ifdef ONBIT
// Na bitach, ograniczenie m<=63 ewentualnie m<=64
double komb(unsigned n,unsigned m,double *M)
{
double result=0;
unsigned long long tb=(1LL<<n)-1; // m<=63 aby powiększyć do 64 -> // tb=(((1LL<<(n-1))-1)<<1)|1;
while(true)
{
unsigned i;
unsigned long long p;
double add=1;
for(i=0,p=1;i<m;++i,p<<=1) if(tb&p) add*=M[i];
result+=add;
for(i=0,p=1LL<<(m-1);(p)&&(p&tb);tb^=p,p>>=1) ++i;
while((p)&&(!(p&tb))) p>>=1;
if(!p) break;
tb^=p;
while(i--<n) tb|=(p<<=1);
}
return result;
}
#else
// Bez ograniczeń, ale z dodatkowym przydzieleniem pamięci
double komb(unsigned n,unsigned m,double *M)
{
double result=0;
unsigned *tb=new unsigned[n];
for(unsigned i=0;i<n;++i) tb[i]=i;
while(true)
{
double add=1;
for(unsigned i=0;i<n;++i) add*=M[tb[i]];
result+=add;
unsigned i=n-1,p=m;
while((i<n)&&(tb[i]>=--p)) --i;
if(i>=n) break;
p=++tb[i];
while(++i<n) tb[i]=++p;
}
delete[] tb;
return result;
}
#endif
int main()
{
while(true)
{
cout<<"Podaj n m (!-konec): ";
unsigned n,m;
if(cin>>n>>m)
{
if(n<=m)
{
double *M=new double[m];
for(unsigned i=0;i<m;)
{
cout<<"M["<<(i+1)<<"]=";
cin.sync();
if(cin>>M[i]) ++i;
else
{
cin.clear();
cout<<"Blad wprowadzenia"<<endl<<endl;
}
}
cout<<"wynik="<<komb(n,m,M)<<';';
delete[] M;
}
else cout<<"n nie moze byc wieksza od m";
}
else
{
cin.clear();
if(cin.get()=='!') return 0;
cout<<"Blad wprowadzenia";
}
cin.sync();
cout<<endl<<endl;
}
}
EDIT: Dokleiłem również wersje na bitach, wg pomysłu od Xitami (ale bez kombinowania).
Już mówię, do czego było mi to potrzebne: do obliczania współczynników wielomianu interpolacyjnego Newtona :)