function store(o, val, sign, lOp, rOp, goal){
//o[val] = '('+lOp+')'+sign+'('+rOp+')';
o[val] = '';
if(val == goal){
console.timeEnd('start')
console.log('GOOOOOOAL ', o[val]);
process.exit(0);
}
}
/*
for given arr
generate all left|right parts
process all possible results between left and right recursively
dic: partition -> [value->op]
let simplify op as string for now. Later as concatenation of pointer postfix
*/
function dyn(arr, mask, dic, goal){
if(dic[mask])return;
var n = arr.length;
//2^n possibility
//right must contain at least one 1
//that is: ignore 11111
for(var left = 1; left<Math.pow(2, n)-1; ++left){
var right = left^(Math.pow(2,n)-1);
var subl = left & mask;
var subr = right & mask;
if(subl && subr && subl>=subr){ //the partition<left, right> lies in mask
dyn(arr, subl, dic, goal)
dyn(arr, subr, dic, goal)
dic[mask] = {};
Object.keys(dic[subl]).forEach(k=>{
const v = dic[subl][k];
Object.keys(dic[subr]).forEach(l=>{
const w = dic[subr][l];
k = parseInt(k);
l = parseInt(l);
store(dic[mask], k+l, '+', v, w, goal);
store(dic[mask], k*l, '*',v, w, goal);
if(k>l){
store(dic[mask], k-l, '-',v, w, goal);
if(k % l == 0){
store(dic[mask], k/l, '/',v, w, goal);
}
}else{
store(dic[mask], l-k, '-',w, v, goal);
if(l % k == 0){
store(dic[mask], l/k, '/',w, v, goal);
}
}
})
})
}
}
}
/**
* @param {[type]} arr [description]
* @param {[type]} dic
* @return {[type]} [description]
*/
function solve(arr, goal){
var n = arr.length;
var dic = {};
//on every items of arr, add a bit position
for(var i = 0; i<n; ++i){
var mask = Math.pow(2, i);
dic[mask] = {[arr[i]]:arr[i]};
}
console.time('start');
dyn(arr, (Math.pow(2,n)-1), dic, goal)
}
solve([1 ,2, 213, 8 ,9, 18, 107, 82, 90, 12], 1000000)
P.S. : Ton algo, il met combien de temps à énumérer TOUT les cas (si tu t'arrête dès que tu as une solution, je pense pas que ce soit bien pertinent en terme de complexité vu que ça peut être un "coup de bol", sans parler du fait que, s'il y a pas de solution alors il faudra TOUT passer en revue)
function Tree(op,left,right){
this.op = op;
this.left = left;
this.right = right;
this.adders = [];
this.multipliers = [];
if(this.op >=0){this.adders=[op];this.multipliers=[op];}
else{
if(this.op == opMap.PLUS){
this.adders = left.adders.concat(right.adders);
this.multipliers = [this.valadd()];
}else if(this.op == opMap.SUBS){
this.adders = left.adders.concat(right.adders.map(x=>-x).reverse());
this.multipliers = [this.valadd()];
}else if(this.op == opMap.TIME){
this.multipliers = this.left.multipliers.concat(this.right.multipliers);
this.adders = [this.valmul()];
}else if(this.op == opMap.DIVI){
this.multipliers = left.multipliers.concat(right.multipliers.map(x=>-x).reverse());
this.adders = [this.valmul()];
}else{
throw "learn how to code";
}
}
}
#define PLUS_OP -1
#define TIME_OP -2
#define SUBS_OP -3
#define DIVI_OP -4
#include <vector>
#include <map>
#include <sstream>
#include <iostream>
#include <chrono>
#include <bitset>
auto T1_START = std::chrono::high_resolution_clock::now();
class Tree{
public:
Tree(int op, int val=0, const Tree* left=NULL, const Tree* right=NULL):
_op(op),
_val(val),
_left(left),
_right(right){
if(op >= 0){
_val = op;
_rightVal = op;
}else{
_val = val;
if(op == SUBS_OP || op == DIVI_OP){
_rightVal = -val;
}else{
_rightVal = val;
}
}
}
int _op;
size_t _val;
int _rightVal;
const Tree* _left;
const Tree* _right;
std::string toString()const{
if(_op >= 0){
std::stringstream oss;
oss<<_op;
return oss.str();
}
std::stringstream oss;
char symbol;
if(_op==-1){
symbol = '+';
}else if(_op==-2){
symbol = '*';
}else if(_op==-3){
symbol = '-';
}else if(_op==-4){
symbol = '/';
}
oss<<"("<<_left->toString()<<")"<<symbol<<"("<<_right->toString()<<")";
return oss.str();
}
bool isMul()const{
return _op >= 0 || _op == TIME_OP || _op == DIVI_OP;
}
bool isAdd()const{
return _op >= 0 || _op == PLUS_OP || _op == SUBS_OP;
}
static bool isAddOk(const Tree*a, const Tree*b){
return a->_rightVal >= b->_val && b->isMul();
}
static bool isMulOk(const Tree*a, const Tree*b){
return a->_rightVal >= b->_val && b->isAdd();
}
static bool isSubOk(const Tree*a, const Tree*b){
return a->_rightVal >= -b->_val && b->isMul();
}
static bool isDivOk(const Tree*a, const Tree*b){
return a->_rightVal >= -b->_val && b->isAdd();
}
};
typedef std::map<size_t, std::map<size_t, Tree*>> Dic;
void dump(const std::string& s, const Dic &d){
std::cout<<s<<std::endl;
for(const auto& p: d){
std::cout<<p.first<<std::endl;
for(const auto& v: p.second){
std::cout<<"\t"<<v.first<<":"<<v.second->toString()<<std::endl;
}
}
}
void dump(const std::string& s, const size_t &l){
std::bitset<sizeof(l)> b(l);
std::cout<<s<<" "<<b<<std::endl;
}
void print_goal(const std::string& s){
auto t2 = std::chrono::high_resolution_clock::now();
std::cout<<(std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - T1_START).count()/1000000)
<< " ms:"
<< s
<<std::endl;
}
void store_plus(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
if(!Tree::isAddOk(l.second,r.second)){
return;
}
const auto& res = l.first+r.first;
m[res] = new Tree(PLUS_OP, res, l.second, r.second);
if(res == goal){
print_goal(m[res]->toString());
}
}
void store_time(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
const auto& res = l.first*r.first;
if(!Tree::isMulOk(l.second,r.second)){
return;
}
m[res] = new Tree(TIME_OP, res, l.second, r.second);
if(res == goal){
print_goal(m[res]->toString());
}
}
void store_subs(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
const auto& res = l.first-r.first;
if(!Tree::isSubOk(l.second,r.second)){
return;
}
m[res] = new Tree(SUBS_OP, res, l.second, r.second);
if(res == goal){
print_goal(m[res]->toString());
}
}
void store_divi(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
const auto& res = l.first/r.first;
if(!Tree::isDivOk(l.second,r.second)){
return;
}
m[res] = new Tree(DIVI_OP, res, l.second, r.second);
if(res == goal){
print_goal(m[res]->toString());
}
}
size_t MAX_CALLS = 0;
void dyn(const std::vector<size_t>& v, size_t mask, Dic& dic, size_t goal){
//mp("dyncall", mask);
if(dic.find(mask)!=dic.end())return;
//X_CALLS++;
//(MAX_CALLS==5){throw std::string("caca");}
dic[mask];
const auto& n = v.size();
size_t ones = (1<<n)-1;;
size_t umask = mask^ones;
for(size_t left = 1; left<ones; ++left){
size_t right = left^(ones);
size_t subl = left & mask;
size_t subr = right & mask;
if(subl && subr && (umask&left)==0){ //the partition<left, right> lies in mask
dyn(v, subl, dic, goal);
dyn(v, subr, dic, goal);
//dump("bl", subl);
//dump("br", subr);
for(const auto& l: dic[subl]){
for(const auto& r: dic[subr]){
store_plus(dic[mask], l,r,goal);
store_time(dic[mask], l,r,goal);
if(l.first>r.first){
store_subs(dic[mask], l,r,goal);
if(r.first!=0 && l.first % r.first == 0){
store_divi(dic[mask], l,r,goal);
}
}
}
}
}
}
}
void solve(const std::vector<size_t>& v, const int &goal){
Dic dic;
for(size_t i=0;i<v.size(); ++i){
size_t mask = 1 << i;
dic[mask][v[i]] = new Tree(v[i]);
}
dyn(v, (1<<v.size())-1, dic, goal);
for(const auto&p :dic){
for(const auto&q : p.second){
delete q.second;
}
}
}
int main(int argc, char* argv[]){
T1_START = std::chrono::high_resolution_clock::now();
std::vector<size_t> v;
for(size_t i = 1;i<argc-1;++i){
v.push_back(atoi(argv[i]));
}
size_t goal = atoi(argv[argc-1]);
solve(v,goal);
return 0;
}
g++ compte.cpp -O3 -std=c++11 && ./a.out 1 2 213 8 9 18 107 82 90 12 1000000
14 ms:(((107)+(18))*(8))*((((90)+(12))*(9))+(82))
49 ms:(((((90)+(12))*(9))+(82))*(8))*((107)+(18))
71 ms:(((((90)+(12))*(9))+(82))*((107)+(18)))*(8)
531 ms:(((82)*(((18)+(12))+(8)))+(9))*((213)+(107))
1274 ms:((((((90)+(82))*(18))+(12))+(9))+(8))*((213)+(107))
5891 ms:(((((90)*(2))+(107))+(213))*((82)+(18)))*((12)+(8))
6103 ms:(((82)+(18))*((12)+(8)))*((((90)*(2))+(107))+(213))
6298 ms:(((((90)*(2))+(107))+(213))*((12)+(8)))*((82)+(18))
//note: les deux echantillons en dessous sont pa normaux car 8 et 2 intervertis KO
8500 ms:((((((107)*(90))+((213)*(12)))+(9))*(82))+(2))+(8)
8674 ms:((((((107)*(90))+((213)*(12)))+(9))*(82))+(8))+(2)
27690 ms:(((((213)+(90))*(12))*(2))+(((82)+(9))*(8)))*((107)+(18))
41297 ms:((((107)+(18))*(8))*(1))*((((90)+(12))*(9))+(82))
41714 ms:((((((90)+(12))*(9))+(82))*(8))*(1))*((107)+(18))
41933 ms:((((((90)+(12))*(9))+(82))*((107)+(18)))*(1))*(8)
41995 ms:((((((90)+(12))*(9))+(82))*((107)+(18)))*(8))*(1)
48108 ms:((((82)*(((18)+(12))+(8)))+(9))*(1))*((213)+(107))
48481 ms:((((82)*(((18)+(12))+(8)))+(9))*((213)+(107)))*(1)
54872 ms:((((((90)*(8))+(107))*(9))+((213)*(12)))+(1))*((82)+(18))
56937 ms:(((((((90)+(82))*(18))+(12))+(9))+(8))*(1))*((213)+(107))
58687 ms:(((((((90)*(8))+(213))*((107)+(12)))+(82))*(9))+(1))+(18)
59906 ms:((((((((107)+(18))+(8))*(90))+(12))+(213))*(82))+(1))+(9)
62689 ms:((((((((107)+(18))+(8))*(90))+(12))+(213))*(82))+(9))+(1)
62689 ms:(((((((90)+(82))*(18))+(12))+(9))+(8))*((213)+(107)))*(1)
68894 ms:(((107)+(18))*(8))*(((90)*(9))+((((82)+(12))+(1))*(2)))
72313 ms:(((107)+(18))*(8))*(((82)*((9)+(1)))+((90)*(2)))
72441 ms:((((107)*((9)+(1)))+((90)*(2)))*(8))*((82)+(18))
72524 ms:((((82)*((9)+(1)))+((90)*(2)))*(8))*((107)+(18))
72763 ms:((((82)*((9)+(1)))+((90)*(2)))*((107)+(18)))*(8)
76787 ms:((((90)*(9))+((((82)+(12))+(1))*(2)))*(8))*((107)+(18))
80036 ms:((((90)*(9))+((((82)+(12))+(1))*(2)))*((107)+(18)))*(8)
86046 ms:((((213)+(90))*(((12)*(2))+(9)))+(1))*((82)+(18))
87991 ms:((((82)*((18)+(1)))*(2))+(9))*((213)+(107))
90986 ms:((((((90)+(82))+(1))*(18))+(9))+(2))*((213)+(107))
#define PLUS_OP -1
#define TIME_OP -2
#define SUBS_OP -3
#define DIVI_OP -4
#include <vector>
#include <map>
#include <sstream>
#include <iostream>
#include <chrono>
#include <bitset>
auto T1_START = std::chrono::high_resolution_clock::now();
class Tree{
public:
Tree(int op, int val=0, const Tree* left=NULL, const Tree* right=NULL):
_op(op),
_val(val),
_left(left),
_right(right){
if(op >= 0){
_val = op;
_rightVal = op;
}else{
_val = val;
if(op == SUBS_OP || op == DIVI_OP){
_rightVal = -right->_val;
}else{
_rightVal = right->_val;
}
}
}
int _op;
size_t _val;
int _rightVal;
const Tree* _left;
const Tree* _right;
std::string toString()const{
if(_op >= 0){
std::stringstream oss;
oss<<_op;
return oss.str();
}
std::stringstream oss;
char symbol;
if(_op==-1){
symbol = '+';
}else if(_op==-2){
symbol = '*';
}else if(_op==-3){
symbol = '-';
}else if(_op==-4){
symbol = '/';
}
oss<<"("<<_left->toString()<<")"<<symbol<<"("<<_right->toString()<<")";
return oss.str();
}
bool isMul()const{
return _op >= 0 || _op == TIME_OP || _op == DIVI_OP;
}
bool isAdd()const{
return _op >= 0 || _op == PLUS_OP || _op == SUBS_OP;
}
static bool isAddSubOk(const Tree*a, const Tree*b){
if(a->isAdd()){
return a->_rightVal >= b->_val && b->isMul();
}
return a->_val >= b->_val && b->isMul();
}
static bool isMulDivOk(const Tree*a, const Tree*b){
if(a->isAdd()){
return a->_val >= b->_val && b->isAdd();
}
return a->_rightVal >= b->_val && b->isAdd();
}
};
typedef std::map<size_t, std::map<size_t, Tree*>> Dic;
void dump(const std::string& s, const Dic &d){
std::cout<<s<<std::endl;
for(const auto& p: d){
std::cout<<p.first<<std::endl;
for(const auto& v: p.second){
std::cout<<"\t"<<v.first<<":"<<v.second->toString()<<std::endl;
}
}
}
void dump(const std::string& s, const size_t &l){
std::bitset<sizeof(l)> b(l);
std::cout<<s<<" "<<b<<std::endl;
}
void print_goal(const std::string& s){
auto t2 = std::chrono::high_resolution_clock::now();
std::cout<<(std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - T1_START).count()/1000000)
<< " ms:"
<< s
<<std::endl;
}
void dump(const Tree* t, const std::string& prefix = ""){
if(t->_op >= 0){
std::cout<<prefix<<t->_op<<std::endl;
return;
}
std::string sign;
if(t->_op==-1){sign="+";}
if(t->_op==-2){sign="*";}
if(t->_op==-3){sign="-";}
if(t->_op==-4){sign="/";}
std::cout<<"prefix"<<" val:" << t->_val<<" rv:"<<t->_rightVal<<" op:"<<sign<<std::endl;
std::cout<<prefix<<"left"<<std::endl;
dump(t->_left, prefix+" ");
std::cout<<prefix<<"right"<<std::endl;
dump(t->_right, prefix+" ");
}
void store_plus(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
if(!Tree::isAddSubOk(l.second,r.second)){
return;
}
const auto& res = l.first+r.first;
m[res] = new Tree(PLUS_OP, res, l.second, r.second);
if(res == goal){
print_goal(m[res]->toString());
}
}
void store_subs(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
const auto& res = l.first-r.first;
if(!Tree::isAddSubOk(l.second,r.second)){
return;
}
m[res] = new Tree(SUBS_OP, res, l.second, r.second);
if(res == goal){
print_goal(m[res]->toString());
}
}
void store_time(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
const auto& res = l.first*r.first;
if(!Tree::isMulDivOk(l.second,r.second)){
return;
}
m[res] = new Tree(TIME_OP, res, l.second, r.second);
if(res == goal){
print_goal(m[res]->toString());
}
}
void store_divi(Dic::mapped_type& m, const Dic::mapped_type::value_type& l, const Dic::mapped_type::value_type& r, size_t goal){
const auto& res = l.first/r.first;
if(!Tree::isMulDivOk(l.second,r.second)){
return;
}
m[res] = new Tree(DIVI_OP, res, l.second, r.second);
if(res == goal){
print_goal(m[res]->toString());
}
}
size_t MAX_CALLS = 0;
void dyn(const std::vector<size_t>& v, size_t mask, Dic& dic, size_t goal){
if(dic.find(mask)!=dic.end())return;
dic[mask];
const auto& n = v.size();
size_t ones = (1<<n)-1;;
size_t umask = mask^ones;
for(size_t left = 1; left<ones; ++left){
size_t right = left^(ones);
size_t subl = left & mask;
size_t subr = right & mask;
if(subl && subr && (umask&left)==0){ //the partition<left, right> lies in mask
dyn(v, subl, dic, goal);
dyn(v, subr, dic, goal);
//dump("bl", subl);
//dump("br", subr);
for(const auto& l: dic[subl]){
for(const auto& r: dic[subr]){
if(l.first>r.first){
store_plus(dic[mask], l,r,goal);
store_time(dic[mask], l,r,goal);
store_subs(dic[mask], l,r,goal);
if(r.first!=0 && l.first % r.first == 0){
store_divi(dic[mask], l,r,goal);
}
}
}
}
}
}
}
void solve(const std::vector<size_t>& v, const int &goal){
Dic dic;
for(size_t i=0;i<v.size(); ++i){
size_t mask = 1 << i;
dic[mask][v[i]] = new Tree(v[i]);
}
dyn(v, (1<<v.size())-1, dic, goal);
for(const auto&p :dic){
for(const auto&q : p.second){
delete q.second;
}
}
}
int main(int argc, char* argv[]){
T1_START = std::chrono::high_resolution_clock::now();
std::vector<size_t> v;
for(size_t i = 1;i<argc-1;++i){
v.push_back(atoi(argv[i]));
}
size_t goal = atoi(argv[argc-1]);
solve(v,goal);
return 0;
}
496 ms:(((((90)+(12))*(9))+(82))*((107)+(18)))*(8)
4343 ms:(((82)*(((18)+(12))+(8)))+(9))*((213)+(107))
10998 ms:((((((90)+(82))*(18))+(12))+(9))+(8))*((213)+(107))
12364 ms:((((((107)*(90))+((213)*(12)))+(9))*(82))-(8))+(18)
14384 ms:((((((107)*(90))+((213)*(12)))+(9))*(82))+(18))-(8)
17337 ms:(((((90)*(12))-(82))+(2))*((107)+(18)))*(8)
19205 ms:(((107)+(18))*(((12)*(9))-(8)))*((82)-(2))
19280 ms:((((107)*((82)-(9)))*(8))+(12))*((18)-(2))
20551 ms:(((((90)+(8))*(9))-(82))*((107)+(18)))*((12)-(2))
20753 ms:((((82)+(9))*((90)-(2)))-(8))*((107)+(18))
23724 ms:((((((82)*(2))-(90))*(12))*(9))+(8))*((107)+(18))
26098 ms:(((((((107)+(9))*(12))-(2))*(90))-(82))-(18))*(8)
26286 ms:((((((18)*(12))+(107))*((90)+(82)))*(9))*(2))-(8)
32908 ms:(((((213)-(90))*(9))-(107))*((82)+(18)))*((12)-(2))
38228 ms:((((((90)*(18))-(12))*(2))-(82))-(9))*((213)+(107))
46279 ms:((((107)*(18))+(12))*(((213)*(2))+(90)))-(8)
48683 ms:((((213)+((90)*(2)))+(107))*((82)+(18)))*((12)+(8))
49848 ms:((((((213)-(90))*((107)-(8)))+(18))*(82))-(2))+(12)
58503 ms:((((((213)-(90))*((107)-(8)))+(18))*(82))+(12))-(2)
64804 ms:((((107)*(82))-(2))*(((213)-(90))-(9)))-(8)
66677 ms:((((82)*(12))*(9))-((107)*(8)))*(((213)-(90))+(2))
73155 ms:((((((213)+(9))*(90))+(12))+(8))*((107)-(82)))*(2)
73249 ms:((((((107)*(90))+((213)*(12)))+(9))*(82))+(8))+(2)
81106 ms:((((((213)+(9))*(90))+(12))+(8))/(2))*((82)+(18))
81553 ms:((((((90)*(9))+(213))+(18))*(12))+(8))*((82)-(2))
84636 ms:(((((213)+((12)*(9)))+(2))*((90)+(82)))*(18))-(8)
85712 ms:((((((213)+(9))*(90))+(12))+(8))*((82)+(18)))/(2)
89265 ms:(((((213)-(18))-(8))*(107))-(9))*((((82)-(12))*(2))-(90))
^C
static bool isAddSubOk(const Tree*a, const Tree*b){
if(a->isAdd()){
return a->_rightVal >= b->_val && b->isMul();
}
return a->_val >= b->_val && b->isMul();
}
static bool isMulDivOk(const Tree*a, const Tree*b){
if(a->isAdd()){
return a->_val >= b->_val && b->isAdd();
}
return a->_rightVal >= b->_val && b->isAdd();
}
#include <stdio.h>
#include <stdlib.h>
#define NbMax 20
int NbPla, Plaque[NbMax];
signed char Util[NbMax]; // 0=non utilisé; 1=addition/soustraction; 2=multiplication/division
int NbLop,Lop[3*NbMax], NbLopSol,LopSol[3*NbMax];
// Liste des opérations Code=(0x10000 si mult/div + 0x100.Nb_Plaques + Nb_Add/Mult) puis liste
int Prof,Atrouver,EcartMin,NbPlaMax;
int NbCalcul,NbSol,NbTrouve[10000],test[NbMax];
//============================================================================================================
void Affiche(int *Tb, int NbTb )
{ int k,i,nb,nb2,R;
// nb=(Tb[0]>>8)&0xFF; nb2=Tb[0]&0xFF;
// for(i=0;i<NbTb-1;i++) printf("%d , ",Tb[i]); printf("%d [%d,%d]\n",Tb[i],nb,nb2);
k=0; do
{ nb=(Tb[k]>>8)&0xFF; nb2=Tb[k]&0xFF;
if((Tb[k]&0x10000)==0)
{ k++; R=Tb[k++]; printf("%d",R);
for(i=1;i<nb2;i++) { R+=Tb[k]; printf(" + %d",Tb[k++]);}
for( ;i<nb ;i++) { R-=Tb[k]; printf(" - %d",Tb[k++]);}
printf(" = %d ; ",R);
}
else
{ k++; R=Tb[k++]; printf("%d",R);
for(i=1;i<nb2;i++) { R*=Tb[k]; printf(" x %d",Tb[k++]);}
for( ;i<nb ;i++) { R/=Tb[k]; printf(" / %d",Tb[k++]);}
printf(" = %d ; ",R);
}
}
while(k<NbTb);
printf("[%d",Plaque[0]); for(i=1;i<NbPla;i++) printf(",%d",Plaque[i]);
printf("] [%d",Util[0]); for(i=1;i<NbPla;i++) printf(",%d",Util[i]); printf("]");
//scanf("%d",&i);
printf("\n");
}
//============================================================================================================
void SousEnsemble(int *Nb, int k, int max, int m);
void ListeSomme(void)
// Cherche toutes les façons d'écrire NbPla = 1.Nb[1]+2.Nb[2]+3.Nb[3]+...+imax.Nb[imax]
{ int i,imax,Nb[NbMax];
Nb[1]=NbPla; for(i=2;i<=NbPla;i++) Nb[i]=0; imax=2;
do
{ if(Nb[1]>=2){ Nb[1]-=2; Nb[2]++;}
else
{ for(i=2;Nb[i]==0;i++);
if((Nb[1]==1)||(Nb[i]>=2)){ Nb[1]+=i*(Nb[i]-1)-1; Nb[i]=0; Nb[i+1]++;}
else{ Nb[1]=i-1; Nb[i]=0; for(i++;Nb[i]==0;i++); Nb[1]+=i*(Nb[i]-1); Nb[i]=0; Nb[i+1]++;}
if(i==imax) imax++;
}
// test[Prof]++;
// if((test[1]==1)&&(test[2]>17)&&(test[2]<22))
// { char c=' '; printf("%d =",NbPla);
// for(i=1;i<=NbPla;i++) if(Nb[i]){ printf("%c%dx%d ",c,Nb[i],i); c='+';} else printf(" . ");
// printf("\n"); //scanf("%d",&i);
// }
SousEnsemble(Nb,imax,NbPla-1,2);
}
while(Nb[NbPla]==0);
}
void SousEnsemble(int *Nb, int k, int max, int m)
// Cherche un sous ensemble à k éléments de {0..max} dont le maximum est >=k.Nb[k]-1 ; m=N° de l'appel
{ int i,j,k2,j1,E[NbMax],P[NbMax],T1,T2,R; signed char U[NbMax],S[NbMax],OK;
for(i=0;i<k-1;i++) E[i]=i; E[k-1]=k*Nb[k]-1; if(k<NbMax) E[k]=-1;
Nb[k]--; if(Nb[k]>0) k2=0; else { k2=k-1; while((k2>1)&&(Nb[k2]==0)) k2--; }
do
{ if(Prof<2) OK=1; else
{ j1=2-(Prof&1); j=0; for(i=0;i<k;i++) if(Util[E[i]]!=j1) j++;
OK=(j<2);
}
if(OK)
{ for(i=0,j=j1=E[0];j<NbPla;j++) if(j==E[i]){ P[i]=Plaque[j]; U[i] =Util[j]; i++;}
else { Plaque[j1]=Plaque[j]; Util[j1]=Util[j]; j1++;}
for(i=0;i<k;i++) S[i]=0;
do
{ if((Prof&1)==0)
{ T1=T2=0; j1=0; for(i=0;i<k;i++) if(S[i]){ T1+=P[i]; j1++;} else T2+=P[i];
if(T1>T2){ R=T1-T2; OK=1; i=0;} else if(T2>T1){ R=T2-T1; OK=2; i=0;} else OK=0;
}
else
{ T1=T2=1; j1=0; OK=1; for(i=0;i<k;i++){ if((j=P[i])==1) OK=0; if(S[i]){ T1*=j; j1++;} else T2*=j; }
if(OK) if(T1%T2==0){ R=T1/T2; i=1<<16;} else if(T2%T1==0){ R=T2/T1; OK=2; i=1<<16;} else OK=0;
}
if(OK)
{ j=NbLop; if(OK==1)
{ Lop[j++]=i+(k<<8)+j1; j1+=j; for(i=0;i<k;i++) if(S[i]) Lop[j++]=P[i]; else Lop[j1++]=P[i];}
else
{ j1=k-j1; Lop[j++]=i+(k<<8)+j1; j1+=j; for(i=0;i<k;i++) if(S[i]) Lop[j1++]=P[i]; else Lop[j++]=P[i];}
NbLop+=k+1; NbPla-=k-1; Plaque[NbPla-1]=R; Util[NbPla-1]=1+(Prof&1);
for(i=NbPla-2;(i>=0)&&(Util[i]==0);i--);
if((k2==1)&&(i==-1))
{ if((abs(R-Atrouver)<EcartMin)||((abs(R-Atrouver)==EcartMin)&&(NbPla>NbPlaMax)))
{ EcartMin=abs(R-Atrouver); NbPlaMax=NbPla; NbLopSol=NbLop;
for(i=0;i<NbLop;i++) LopSol[i]=Lop[i];
}
NbCalcul++; //if(R<1000) NbTrouve[R]++; // Pour tests...
if(R==Atrouver){ NbSol++; printf("%d) ",NbSol); Affiche(Lop,NbLop); }
}
if(k2==0) SousEnsemble(Nb,k,E[k-1]-k,m+1);
else if(k2>1) SousEnsemble(Nb,k2,NbPla-m,m+1);
else if(NbPla>=2){Prof++; ListeSomme(); Prof--;}
NbPla+=k-1; NbLop-=k+1;
}
for(i=k-1;S[i]!=0;i--) S[i]=0; S[i]=1;
}
while(S[0]==0);
for(i=k-1,j=NbPla-1,j1=NbPla-k-1;j>=E[0];j--)
if(j==E[i]){ Plaque[j]=P[i]; Util[j]=U[i]; i--;}
else { Plaque[j]=Plaque[j1]; Util[j]=Util[j1]; j1--;}
}
for(i=0;(i+1<k)&&(E[i+1]==E[i]+1);i++);
E[i]++; for(j=0;j<i;j++) E[j]=j;
}
while(E[k-1]<=max);
Nb[k]++;
}
int NbLop,Lop[3*NbMax], NbLopSol,LopSol[3*NbMax];
// Liste des opérations Code=(0x10000 si mult/div + 0x100.Nb_Plaques + Nb_Add/Mult) puis liste
int Prof,Atrouver,EcartMin,NbPlaMax;
//============================================================================================================
int main()
{ int i,j,deb;
NbPla=10;
Plaque[0]=1;
Plaque[1]=2;
Plaque[2]=213;
Plaque[3]=8;
Plaque[4]=9;
Plaque[5]=18;
Plaque[6]=107;
Plaque[7]=82;
Plaque[8]=90;
Plaque[9]=12;
Atrouver=1000000;
EcartMin=10000; NbLop=0; for(i=0;i<NbPla;i++) Util[i]=0;
NbCalcul=NbSol=0; for(i=0;i<1000;i++) NbTrouve[i]=0; for(i=0;i<NbMax;i++) test[i]=0;
Prof=0; ListeSomme(); printf("-------------------------------------------------------------------------\n");
Prof=1; ListeSomme(); //-> ne fait aucune addition préalable
printf("NbCalcul = %d\n",NbCalcul);
Affiche(LopSol,NbLopSol);
/*for(j=0;j<20;j++)
{ deb=1;
for(i=100;i<999;i++)
if(NbTrouve[i]==j) if(deb) { printf("%2d : %d",j,i); deb=0; } else printf(",%d",i);
if(!deb) printf("\n");
}
*/
}
Mais ça doit être passablement illisible (comme d'hab...)
Vu que ça fait je sais pas combien d'années que j'ai tapé le bidule, ben... je peine pas mal à retrouver comment ça marche.fatal_error a écrit:Peux tu expliquer dans le gros SousEnsemble?
j'ai essayé de lire un peu mais jpense qu'il me faudrait au moins un weekend pour décrypter
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 6 invités
Tu pars déja ?
Identification
Pas encore inscrit ?
Ou identifiez-vous :