![]() |
| | #1 |
| Guest
Posts: n/a
| A Simple (?) Problem It comes in a number of parts: ****** Part One: Definitons. I know how to define things in C++, but I am including this part here so you know what I am talking about later. a=1, b=2, c=3, d=4, e=5, f=6 --------- Part Two: Arithmetic. a*{d,e,f} + b{d,e,f} + c*{d,e,f} = z (now, by { }, I mean to try all combinations of these variables: a*d + b*d + c*d is one combination, and a*d + b*d + c*e is another. There are 27 combinations, I believe) if z=20, then continue to next part if not, then go back up and continue trying combinations until you reach a combination where z=20 (and there is more than one combination where z=20) ----------- Part Three: Tests. For each combination found where z=20, I want a number of tests to be done. What was multiplied by a (either d, e, or f) cannot equal what was multiplied by c. What was multiplied by b (either d, e, or f) cannot equal what was multiplied by c. if one test is failed, continue with combinations. if all tests are passed, print the d/e/f values of a, b, and c (in other words, which variables a, b, and c were multiplied by) ****** I don't need an exact working program, but if anyone could help me out with little bits and pieces, or certain topics I should study to figure out how to complete this. Also: Is it more logical that part two should accumulate all values of z=20 and then test those in part three, or would it be better that when a z=20 value is found, part three is carried out (and if that combination does not pass all the tests, return to part two)? I would prefer the latter. I'm sorry if this all seems confusing. I don't know any other way to word it. Like I said, *any* help would be appreciated regardless of how detailed it is. Thanks in advance! Selwyn McPherson. If you have any questions, you can email me at slcool@neo.rr.com |
|
| | #2 |
| geek Join Date: Aug 2001 Location: NJ
Posts: 1,141
| Heh, that's not such a simple problem. How much generality are you aiming for? Do you want it to just be able to solve that specific problem? Is input going to be parsed from a string, or directly incorporated into the code itself? Have you ever written a program to evulate a simple expression, IE, 4+3*3, such would be a good start for this project.
__________________ Prove you can code in C++ or C# at TopCoder, referrer rrenaud Read my livejournal |
| SilentStrike is offline | |
| | #3 |
| Guest
Posts: n/a
| No, there won't be any input. It will just run from the code. I can write programs for simple expressions, yes. This isn't the *actual* problem, no - the actual problem has many more variables and tests, but if I know how to do just a simple one, I can expand it to fit the real problem. Thanks a lot )Selwyn McPherson slcool@neo.rr.com |
|
| | #4 | |
| Registered User Join Date: Aug 2001
Posts: 154
| Quote:
although I've never seen a C++ expression like a * {d, e, f} | |
| Brown Drake is offline | |
| | #5 |
| Registered User Join Date: Aug 2001
Posts: 72
| just an idea how to enumerate all possible combinations Code:
// digit[0] is a, digit[1] is b ... digit[5] is f
int digits[6] = {1,2,3,4,5,6};
int z = 0;
for (int d = 3; d < 6; d++)
for (int e = 3; e < 6; e++)
for (int f = 3; f < 6; f++)
{
z = digit[0]*digit[d]+
digit[1]*digit[e]+
digit[2]*digit[f];
if (z == 20)
{
// do whatever you like
} // end if(z==20)
} // end for(f)
|
| damyan is offline | |
| | #6 |
| Guest
Posts: n/a
| Damyan, thanks for the idea. I will test it out and see if I can get it to work. While I was thinking, I had another way of thinking of it. There's really no need to define a, b, c, etc. in part one. In part two, it would be easier to just use ----- 1*{4,5,6} + 2*{4,5,6} + 3*{4,5,6} etc. ----- For each combinations, though, I need to set the value of { } as a variable. That would make it easier to test in part three. ----- 1*{4,5,6} (now assign either the 4, 5, or 6 as x) + 2*{4,5,6} (now assign either the 4, 5, or 6 as y) + 3*{4,5,6} (now assign either the 4, 5, or 6 as z) ----- To test: x cannot equal z y cannot equal z and so forth. I don't know if that's possible, though. I also had another concern. When z does not equal 20, and the process of finding combinations continues, will it restart? Will it pick up from where it left off? Restarting wouldn't be very productive; the program would just keep trying the same combination over and over again. Again, I'm sorry if my wording or ideas seem confusing. :-/ I appreciate everyone's brain cells :-) Selwyn McPherson. slcool@neo.rr.com |
|
| | #7 |
| Registered User Join Date: Aug 2001
Posts: 72
| so you don't need all possible combination over the {def} elements instead, you need all the permutations over them so here is an example of enumerating all the permuatations using the STL Code: #include <vector>
#include <algorithm>
using namespace std ;
void main()
{
// declarations
vector<int> intV;
vector<int>::iterator it;
// initialization
for(int i = 4;i< 7; i++)
intV.push_back(i);
int j, z = 0;
// enum permutations
while ( next_permutation(intV.begin(), intV.end()) )
{
z = 0; //calc z
for (j = 1, it=intV.begin(); it != intV.end(); it++, j++)
z+=j*(*it);
if (z == 20)
{
// do the job
} // end (if match)
} // end while(have more permutations)
it = it;
} // end main
Last edited by damyan; 10-12-2001 at 01:48 AM. |
| damyan is offline | |
| | #8 |
| Guest
Posts: n/a
| I think I eventually got it to work. The actual problem is to figure out how to paint a map of the USA with four colors, where no two colors touch. It is possible, and that is just the easy part. The second part is that each of the four paints costs a different amount ($1, $2, $3, and $4), and I've got to try to figure out the lowest possible combination. The lowest price possible is $5926 (I've been told - I hope this is right). I used a bunch (48) FOR loops for the combinations, and 100 or so if statements for the tests (to make sure that states of the same color don't touch). The problem is, there are 4^48 possible combinations, so I don't know how long this will take. It doesn't have to go through all of those combinations, mind you, but it still might take a long time. The code may seem a little messy or silly, but I don't know any better :-) <code> #include <iostream.h> int main() { int AL = 52; int AZ = 114; int AK = 53; int CA = 159; int CO = 104; int CT = 5; int DL = 2; int FL = 59; int GA = 59; int ID = 84; int IL = 56; int IN = 36; int IO = 56; int KA = 82; int KT = 40; int LO = 49; int MA = 33; int MD = 11; int MC = 8; int MI = 58; int MN = 84; int MP = 48; int MS = 70; int MT = 147; int NB = 77; int NV = 111; int NH = 9; int NJ = 8; int NM = 122; int NY = 50; int NC = 53; int ND = 71; int OH = 41; int OK = 70; int OR = 97; int PA = 45; int RI = 1; int SC = 31; int SD = 77; int TN = 42; int TX = 267; int UT = 85; int VA = 41; int VT = 10; int WA = 68; int WV = 24; int WI = 56; int WY = 98; int aa = 0; int ab = 0; int ac = 0; int ad = 0; int ae = 0; int af = 0; int ag = 0; int ah = 0; int ai = 0; int aj = 0; int ak = 0; int al = 0; int am = 0; int an = 0; int ao = 0; int ap = 0; int aq = 0; int ar = 0; int as = 0; int at = 0; int au = 0; int av = 0; int aw = 0; int ax = 0; int ay = 0; int az = 0; int ba = 0; int bb = 0; int bc = 0; int bd = 0; int be = 0; int bf = 0; int bg = 0; int bh = 0; int bi = 0; int bj = 0; int bk = 0; int bl = 0; int bm = 0; int bn = 0; int bo = 0; int bp = 0; int bq = 0; int br = 0; int bs = 0; int bt = 0; int bu = 0; int bv = 0; int z = 0; for (int aa = 1; aa < 5; aa++) for (int ab = 1; ab < 5; ab++) for (int ac = 1; ac < 5; ac++) for (int ad = 1; ad < 5; ad++) for (int ae = 1; ae < 5; ae++) for (int af = 1; af < 5; af++) for (int ag = 1; ag < 5; ag++) for (int ah = 1; ah < 5; ah++) for (int ai = 1; ai < 5; ai++) for (int aj = 1; aj < 5; aj++) for (int ak = 1; ak < 5; ak++) for (int al = 1; al < 5; al++) for (int am = 1; am < 5; am++) for (int an = 1; an < 5; an++) for (int ao = 1; ao < 5; ao++) for (int ap = 1; ap < 5; ap++) for (int aq = 1; aq < 5; aq++) for (int ar = 1; ar < 5; ar++) for (int as = 1; as < 5; as++) for (int at = 1; at < 5; at++) for (int au = 1; au < 5; au++) for (int av = 1; av < 5; av++) for (int aw = 1; aw < 5; aw++) for (int ax = 1; ax < 5; ax++) for (int ay = 1; ay < 5; ay++) for (int az = 1; az < 5; az++) for (int ba = 1; ba < 5; ba++) for (int bb = 1; bb < 5; bb++) for (int bc = 1; bc < 5; bc++) for (int bd = 1; bd < 5; bd++) for (int be = 1; be < 5; be++) for (int bf = 1; bf < 5; bf++) for (int bg = 1; bg < 5; bg++) for (int bh = 1; bh < 5; bh++) for (int bi = 1; bi < 5; bi++) for (int bj = 1; bj < 5; bj++) for (int bk = 1; bk < 5; bk++) for (int bl = 1; bl < 5; bl++) for (int bm = 1; bm < 5; bm++) for (int bn = 1; bn < 5; bn++) for (int bo = 1; bo < 5; bo++) for (int bp = 1; bp < 5; bp++) for (int bq = 1; bq < 5; bq++) for (int br = 1; br < 5; br++) for (int bs = 1; bs < 5; bs++) for (int bt = 1; bt < 5; bt++) for (int bu = 1; bu < 5; bu++) for (int bv = 1; bv < 5; bv++) { z = AL*aa + AZ*ab + AK*ac + CA*ad + CO*ae + CT*af + DL*ag + FL*ah + GA*ai + ID*aj + IL*ak + IN*al + IO*am + KA*an + KT*ao + LO*ap + MA*aq + MD*ar + MC*as + MI*at + MN*au + MP*av + MS*aw + MT*ax + NB*ay + NV*az + NH*ba + NJ*bb + NM*bc + NY*bd + NC*be + ND*bf + OH*bg + OK*bh + OR*bi + PA*bj + RI*bk + SC*bl + SD*bm + TN*bn + TX*bo + UT*bp + VA*bq + VT*br + WA*bs + WV*bt + WI*bu + WY*bv; if (z == 5926) { if (bs != aj) { if (bs != bi) { if (bi != ad) { if (bi != bd) { if (bi != aj) { if (ad != az) { if (ad != ab) { if (az != ab) { if (az != bp) { if (az != aj) { if (aj != ax) { if (aj != bv) { if (aj != bp) { if (bp != ab) { if (bp != ae) { if (ab != bc) { if (ax != bv) { if (ax != bf) { if (ax != bm) { if (bv != ae) { if (bv != bm) { if (bv != ay) { if (ae != bc) { if (ae != ay) { if (ae != an) { if (ae != bh) { if (bc != bo) { if (bc != bh) { if (bf != bm) { if (bf != au) { if (bm != au) { if (bm != am) { if (bm != ay) { if (ay != am) { if (ay != an) { if (ay != aw) { if (an != aw) { if (an != bh) { if (bh != bo) { if (bh != ac) { if (au != bu) { if (au != am) { if (am != bu) { if (am != ak) { if (am != aw) { if (aw != ac) { if (aw != ak) { if (aw != ao) { if (aw != bn) { if (ac != bn) { if (ac != av) { if (ac != ap) { if (bo != ap) { if (ap != av) { if (bu != ak) { if (bu != at) { if (ak != al) { if (ak != ao) { if (al != bg) { if (al != ao) { if (al != at) { if (ao != bg) { if (ao != bt) { if (ao != bq) { if (ao != bn) { if (bn != bq) { if (bn != be) { if (bn != ai) { if (bn != aa) { if (bn != av) { if (av != aa) { if (aa != ai) { if (aa != ah) { if (ah != ai) { if (ai != bl) { if (ai != be) { if (bl != be) { if (be != bq) { if (bq != bt) { if (bq != ar) { if (bt != bg) { if (bt != bj) { if (bt != ar) { if (bg != bj) { if (bg != at) { if (bj != ar) { if (bj != bd) { if (bj != bb) { if (bj != ag) { if (ar != ag) { if (bb != bd) { if (bd != br) { if (bd != as) { if (br != af) { if (br != ba) { if (br != as) { if (ba != as) { if (ba != aq) { if (as != bk) { if (af != bk) { if (af != as) { cout << aa << endl; cout << ab << endl; cout << ac << endl; cout << ad << endl; cout << ae << endl; cout << af << endl; cout << ag << endl; cout << ah << endl; cout << ai << endl; cout << aj << endl; cout << ak << endl; cout << al << endl; cout << am << endl; cout << an << endl; cout << ao << endl; cout << ap << endl; cout << aq << endl; cout << ar << endl; cout << as << endl; cout << at << endl; cout << au << endl; cout << av << endl; cout << aw << endl; cout << ax << endl; cout << ay << endl; cout << az << endl; cout << ba << endl; cout << bb << endl; cout << bc << endl; cout << bd << endl; cout << be << endl; cout << bf << endl; cout << bg << endl; cout << bh << endl; cout << bi << endl; cout << bj << endl; cout << bk << endl; cout << bl << endl; cout << bm << endl; cout << bn << endl; cout << bo << endl; cout << bp << endl; cout << bq << endl; cout << br << endl; cout << bs << endl; cout << bt << endl; cout << bu << endl; cout << bv << endl; cout <<" " << endl; } else { } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } return 0; } <code> If anything looks wrong, it'd be nice to know before I wait an eternity for the program to finish only to find no results :-) Thanks a lot for everyone's help so far! Selwyn McPherson. slcool@neo.rr.com |
|
| | #9 |
| Guest
Posts: n/a
| Yikes. That's what you get for not previewing. Sorry about that. Let me try again. Code: #include <iostream.h>
int main()
{
int AL = 52;
int AZ = 114;
int AK = 53;
int CA = 159;
int CO = 104;
int CT = 5;
int DL = 2;
int FL = 59;
int GA = 59;
int ID = 84;
int IL = 56;
int IN = 36;
int IO = 56;
int KA = 82;
int KT = 40;
int LO = 49;
int MA = 33;
int MD = 11;
int MC = 8;
int MI = 58;
int MN = 84;
int MP = 48;
int MS = 70;
int MT = 147;
int NB = 77;
int NV = 111;
int NH = 9;
int NJ = 8;
int NM = 122;
int NY = 50;
int NC = 53;
int ND = 71;
int OH = 41;
int OK = 70;
int OR = 97;
int PA = 45;
int RI = 1;
int SC = 31;
int SD = 77;
int TN = 42;
int TX = 267;
int UT = 85;
int VA = 41;
int VT = 10;
int WA = 68;
int WV = 24;
int WI = 56;
int WY = 98;
int aa = 0;
int ab = 0;
int ac = 0;
int ad = 0;
int ae = 0;
int af = 0;
int ag = 0;
int ah = 0;
int ai = 0;
int aj = 0;
int ak = 0;
int al = 0;
int am = 0;
int an = 0;
int ao = 0;
int ap = 0;
int aq = 0;
int ar = 0;
int as = 0;
int at = 0;
int au = 0;
int av = 0;
int aw = 0;
int ax = 0;
int ay = 0;
int az = 0;
int ba = 0;
int bb = 0;
int bc = 0;
int bd = 0;
int be = 0;
int bf = 0;
int bg = 0;
int bh = 0;
int bi = 0;
int bj = 0;
int bk = 0;
int bl = 0;
int bm = 0;
int bn = 0;
int bo = 0;
int bp = 0;
int bq = 0;
int br = 0;
int bs = 0;
int bt = 0;
int bu = 0;
int bv = 0;
int z = 0;
for (int aa = 1; aa < 5; aa++)
for (int ab = 1; ab < 5; ab++)
for (int ac = 1; ac < 5; ac++)
for (int ad = 1; ad < 5; ad++)
for (int ae = 1; ae < 5; ae++)
for (int af = 1; af < 5; af++)
for (int ag = 1; ag < 5; ag++)
for (int ah = 1; ah < 5; ah++)
for (int ai = 1; ai < 5; ai++)
for (int aj = 1; aj < 5; aj++)
for (int ak = 1; ak < 5; ak++)
for (int al = 1; al < 5; al++)
for (int am = 1; am < 5; am++)
for (int an = 1; an < 5; an++)
for (int ao = 1; ao < 5; ao++)
for (int ap = 1; ap < 5; ap++)
for (int aq = 1; aq < 5; aq++)
for (int ar = 1; ar < 5; ar++)
for (int as = 1; as < 5; as++)
for (int at = 1; at < 5; at++)
for (int au = 1; au < 5; au++)
for (int av = 1; av < 5; av++)
for (int aw = 1; aw < 5; aw++)
for (int ax = 1; ax < 5; ax++)
for (int ay = 1; ay < 5; ay++)
for (int az = 1; az < 5; az++)
for (int ba = 1; ba < 5; ba++)
for (int bb = 1; bb < 5; bb++)
for (int bc = 1; bc < 5; bc++)
for (int bd = 1; bd < 5; bd++)
for (int be = 1; be < 5; be++)
for (int bf = 1; bf < 5; bf++)
for (int bg = 1; bg < 5; bg++)
for (int bh = 1; bh < 5; bh++)
for (int bi = 1; bi < 5; bi++)
for (int bj = 1; bj < 5; bj++)
for (int bk = 1; bk < 5; bk++)
for (int bl = 1; bl < 5; bl++)
for (int bm = 1; bm < 5; bm++)
for (int bn = 1; bn < 5; bn++)
for (int bo = 1; bo < 5; bo++)
for (int bp = 1; bp < 5; bp++)
for (int bq = 1; bq < 5; bq++)
for (int br = 1; br < 5; br++)
for (int bs = 1; bs < 5; bs++)
for (int bt = 1; bt < 5; bt++)
for (int bu = 1; bu < 5; bu++)
for (int bv = 1; bv < 5; bv++)
{
z = AL*aa + AZ*ab + AK*ac + CA*ad + CO*ae + CT*af + DL*ag + FL*ah +
GA*ai + ID*aj + IL*ak + IN*al + IO*am + KA*an + KT*ao + LO*ap +
MA*aq + MD*ar + MC*as + MI*at + MN*au + MP*av + MS*aw + MT*ax +
NB*ay + NV*az + NH*ba + NJ*bb + NM*bc + NY*bd + NC*be + ND*bf +
OH*bg + OK*bh + OR*bi + PA*bj + RI*bk + SC*bl + SD*bm + TN*bn +
TX*bo + UT*bp + VA*bq + VT*br + WA*bs + WV*bt + WI*bu + WY*bv;
if (z == 5926)
{
if (bs != aj) {
if (bs != bi) {
if (bi != ad) {
if (bi != bd) {
if (bi != aj) {
if (ad != az) {
if (ad != ab) {
if (az != ab) {
if (az != bp) {
if (az != aj) {
if (aj != ax) {
if (aj != bv) {
if (aj != bp) {
if (bp != ab) {
if (bp != ae) {
if (ab != bc) {
if (ax != bv) {
if (ax != bf) {
if (ax != bm) {
if (bv != ae) {
if (bv != bm) {
if (bv != ay) {
if (ae != bc) {
if (ae != ay) {
if (ae != an) {
if (ae != bh) {
if (bc != bo) {
if (bc != bh) {
if (bf != bm) {
if (bf != au) {
if (bm != au) {
if (bm != am) {
if (bm != ay) {
if (ay != am) {
if (ay != an) {
if (ay != aw) {
if (an != aw) {
if (an != bh) {
if (bh != bo) {
if (bh != ac) {
if (au != bu) {
if (au != am) {
if (am != bu) {
if (am != ak) {
if (am != aw) {
if (aw != ac) {
if (aw != ak) {
if (aw != ao) {
if (aw != bn) {
if (ac != bn) {
if (ac != av) {
if (ac != ap) {
if (bo != ap) {
if (ap != av) {
if (bu != ak) {
if (bu != at) {
if (ak != al) {
if (ak != ao) {
if (al != bg) {
if (al != ao) {
if (al != at) {
if (ao != bg) {
if (ao != bt) {
if (ao != bq) {
if (ao != bn) {
if (bn != bq) {
if (bn != be) {
if (bn != ai) {
if (bn != aa) {
if (bn != av) {
if (av != aa) {
if (aa != ai) {
if (aa != ah) {
if (ah != ai) {
if (ai != bl) {
if (ai != be) {
if (bl != be) {
if (be != bq) {
if (bq != bt) {
if (bq != ar) {
if (bt != bg) {
if (bt != bj) {
if (bt != ar) {
if (bg != bj) {
if (bg != at) {
if (bj != ar) {
if (bj != bd) {
if (bj != bb) {
if (bj != ag) {
if (ar != ag) {
if (bb != bd) {
if (bd != br) {
if (bd != as) {
if (br != af) {
if (br != ba) {
if (br != as) {
if (ba != as) {
if (ba != aq) {
if (as != bk) {
if (af != bk) {
if (af != as) {
cout << aa << endl;
cout << ab << endl;
cout << ac << endl;
cout << ad << endl;
cout << ae << endl;
cout << af << endl;
cout << ag << endl;
cout << ah << endl;
cout << ai << endl;
cout << aj << endl;
cout << ak << endl;
cout << al << endl;
cout << am << endl;
cout << an << endl;
cout << ao << endl;
cout << ap << endl;
cout << aq << endl;
cout << ar << endl;
cout << as << endl;
cout << at << endl;
cout << au << endl;
cout << av << endl;
cout << aw << endl;
cout << ax << endl;
cout << ay << endl;
cout << az << endl;
cout << ba << endl;
cout << bb << endl;
cout << bc << endl;
cout << bd << endl;
cout << be << endl;
cout << bf << endl;
cout << bg << endl;
cout << bh << endl;
cout << bi << endl;
cout << bj << endl;
cout << bk << endl;
cout << bl << endl;
cout << bm << endl;
cout << bn << endl;
cout << bo << endl;
cout << bp << endl;
cout << bq << endl;
cout << br << endl;
cout << bs << endl;
cout << bt << endl;
cout << bu << endl;
cout << bv << endl;
cout <<" " << endl;
}
else {
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
return 0;
}
slcool@neo.rr.com |
|
![]() |
| Thread Tools | |
| Display Modes | |
|
Similar Threads | ||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Problem in simple code. | richdb | C Programming | 6 | 03-20-2006 02:45 AM |
| Problem in very simple code | richdb | C Programming | 22 | 01-14-2006 09:10 PM |
| A simple file I/O problem | eecoder | C Programming | 8 | 01-12-2006 10:07 AM |
| Simple Initialization Problem | PsyK | C++ Programming | 7 | 04-30-2004 07:37 PM |
| Simple OO Problem | bstempi | C++ Programming | 1 | 04-30-2004 05:33 PM |