C++: bitset инкримент

если имеется ввиду размер, то IMHO использовать boost::dynamic_bitset :)

http://www.boost.org/libs/dynamic_bitset/dynamic_bitset.html

// wbr

Нет, битовое число имеется в виду.

> Нет, битовое число имеется в виду.

"битовое число" - это, пардон, кто? :) если значение Nго бита, то bitset::flip(N)

ps: http://www.sgi.com/tech/stl/bitset.html однако..

// wbr

Задачу оптимизирую. Очень неудачно её сделал...
Надо найти такие знаки + и -, чтобы получилось заданное число. С малым кол-вом чисел програ работает нормально.

С файлом:
24
8593682 31716735 21491280 17902794 33317802 31903797 43140236 27960611 49962940 89871 21765518 824859 10008534 49081942 37138133 10339902 46783173 45482021 19050964 36953244 15710201 13017280 32752188 4020978
-80507031

Надо расставить знаки + и - в эти числа так, чтобы результат был -80507031

прога работает очень долго... мало того, что цикл в 200 миллионов...

Вот код:
#include <fstream>

#include <bitset>

#include <vector>

#include <cmath>

#include <iostream>

using namespace std;



bitset<24> int2bin(int n)

{

	return bitset<24>((long)n);

}



int main(int argc, char **argv)

{

	int N;

	vector<int> numbers;

	int result;

	int found=false;

	

	ifstream f(argv[1]);

	f >> N;

	for(int i=0; i<N; i++)

	{

		int buff;

		f >> buff;

		numbers.push_back(buff);	

	}

	f >> result;

	f.close();

	

	int end = 0;

	for(double i=0; i<N-1; i++)

		end += (int)pow(2.0,i);

	end++;

	

	ofstream out("summa.val");

	cout << end << endl;

	for(int start=0; start<end; start++)

	{

		int sum=0;

		bitset<24> plmin;

		plmin = int2bin(start);

		for(int i=0; i<N; i++)

		{

			if(i==0)

			{

				sum += numbers.at(i);

				continue;

			}

			

			if(plmin[i-1]==0)

			{				

				sum -= numbers.at(i);

			}else{

				sum += numbers.at(i);

			}

		}

		if(sum==result)

		{

			found = true;

			for(int i=0; i<N; i++)

			{

				string s="=";

				if(i!=N-1)

				{

					if(plmin[i]==1)

						s = "+";

					else

						s = "-";

				}

				cout << numbers[i] << s;	

			}

			cout << sum << endl;

		}

	}

	

	if(!found) cout << "EI OLE" << endl;

	return 0;	

}

форматирование просто 3.14здец

Stl и быстрые вычисления не совместимы:)
Если простым перебором, то цикл будет в 16 миллионов итераций.
Вот код на с
#include <stdio.h>
int main(){
__uint32_t a=0;
int mas[]={8593682,31716735,21491280,17902794,33317802,31903797,43140236,27960611,49 962940,89871,21765518,824859,10008534,49081942,37138133,10339902,46783173,454820 21,19050964,36953244,15710201,13017280,32752188,4020978};
int size=24;
int need=-80507031;
int res;
int k=0;
int mov=0;
int max=1<<24;
while(!(a&max)){
a++;
res=0;
for(res=0,k=0,mov=1;k<24;++k){
if(a&mov)
res+=mas[k];
else
res-=mas[k];
mov<<=1;
//printf("mov=%x res=%x",mov,res);
}
if(res==need)
printf("Found!!! %x %d %d",a,a,res);

}
return 0;
}


krum@krum:~$ time ./a.out
Found!!! 896103 9003267 -80507031
real 0m4.629s
user 0m4.208s
sys 0m0.033s

>форматирование просто 3.14здец

На ЛОР-е что-то случилось. Лишние пустые строки не мои...

В условиях задачи - 1 секунда максимум :/

Selecter : читай Кнута и др. про множества и деревья - это классическая задачка и есть в любом учебнике.

извратное решение. тоже полный перебор, но без операций с битами :)
/*$Id: number_signs.c 135 2005-12-23 12:01:50Z manwe $*/
/*
  задача о числах. надо расставить знаки в последовательности
  8593682 31716735 21491280 17902794 33317802 31903797 43140236
  27960611 49962940 89871 21765518 824859 10008534 49081942 37138133
  10339902 46783173 45482021 19050964 36953244 15710201 13017280
  32752188 4020978 
  так, чтобы получилось число
  -80507031
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct tree_node_
{
	int value_;
	int sum_;
	struct tree_node_ *up_;
	struct tree_node_ *left_;
	struct tree_node_ *right_;
} number;

void free_node(number * node)
{
	if (node && node->up_ && node->left_ == 0 && node->right_ == 0)
	{		
		if (node->up_->left_ == node) {
			node->up_->left_ = 0;
		} else {
			node->up_->right_ = 0;
		}
		free(node);
		free_node(node->up_);
	}
}

number * add(number * node, int * nums, int i, int n, int otv)
{
	number * o = 0;
	node->left_          = malloc(sizeof(number));
	node->right_         = malloc(sizeof(number));
	node->left_->left_   = 0;
	node->left_->right_  = 0;
	node->left_->left_   = 0;
	node->right_->right_ = 0;
	node->left_->up_     = node;
	node->right_->up_    = node;
	node->left_->value_  = +nums[i];
	node->right_->value_ = -nums[i];
	node->left_->sum_ =
		node->sum_ + node->left_->value_;
	node->right_->sum_ =
		node->sum_ + node->right_->value_;
	if (i < n - 1) {		
		o = add(node->left_,  nums, i + 1, n, otv);
		if (!o)
			o = add(node->right_, nums, i + 1, n, otv);
	} else {
		if (node->right_->sum_ == otv) {
			return node->right_;
		} else if (node->left_->sum_  == otv) {
			return node->left_;
		} else {
			free(node->left_);
			free(node->right_);
			node->left_ = node->right_ = 0;
			free_node(node);			
		}
	}
	return o;
}

void print_solution(number * n, int otv)
{
	if (n == 0) {
		printf("no solution\n");
		return;
	}
	printf("sum = %d\n", otv); 
	while (n) {
		printf("%d, ", n->value_);
		n = n->up_;
	}
	printf("\n");
}

void solve(int * nums, int n, int otv)
{
	number * otvet = 0;
	number * head  = malloc(sizeof(number));
	head->up_    = 0;
	head->value_ = 0;
	head->sum_   = 0;
	head->left_  = 0;
	head->right_ = 0;
	printf("building tree\n");
	otvet = add(head, nums, 0, n, otv);
	printf("done\n");
	printf("printing solution\n");
	print_solution(otvet, otv);
}

int main() {
	int nums [] = {
		8593682, 31716735, 21491280, 17902794, 33317802, 31903797, 43140236,
		27960611, 49962940, 89871, 21765518, 824859, 10008534, 49081942,
		37138133, 10339902, 46783173, 45482021, 19050964, 36953244,
		15710201, 13017280, 32752188, 4020978
	}; 

	int otv = -80507031;
	solve(nums, sizeof(nums) / sizeof(int), otv);
	return 0;
}

$ time ./number_signs.exe
building tree
done
printing solution
sum = -80507031
4020978, -32752188, -13017280, -15710201, 36953244, -19050964, -45482021, 467831
73, -10339902, 37138133, 49081942, -10008534, -824859, -21765518, -89871, 499629
40, -27960611, -43140236, -31903797, -33317802, -17902794, -21491280, 31716735,
8593682, 0,

real    0m2.837s
user    0m0.031s
sys     0m0.000s

[user@localhost temp]# cat ./tree.c
#include <stdio.h>

int tree(int otv, int cur, int*num)
{
if(*num == 0) return cur == otv;
if(tree(otv, cur + *num, num+1) != 0) return printf("+%d",*num),1;
if(tree(otv, cur - *num, num+1) != 0) return printf("-%d",*num),1;
return 0;
}
int main(void)
{
int nums [] = {
8593682, 31716735, 21491280, 17902794, 33317802, 31903797, 43140236,
27960611, 49962940, 89871, 21765518, 824859, 10008534, 49081942,
37138133, 10339902, 46783173, 45482021, 19050964, 36953244,
15710201, 13017280, 32752188, 4020978, 0
};
int otv = -80507031;
return printf("\n%sfound.\n", (tree(otv, 0, nums) == 0) ? "Not ": "");
}
[user@localhost temp]# time ./tree
+4020978-32752188-13017280-15710201+36953244-19050964-45482021+46783173-10339902 +37138133+49081942-10008534-824859-21765518-89871+49962940-27960611-43140236-319 03797-33317802-17902794-21491280+31716735+8593682
found.

real 0m0.326s
user 0m0.300s
sys 0m0.000s