Я пишу программу, чтобы найти, могу ли я сделать квадрат с N палками N длины.
Я использовал Бит-маску, потому что это легче для большого вклада, который я вставлю туда. По какой-то причине мой код возврата не возвращает ничего, в этой строке «битовая маска» & (1 << vec [i]) «это никогда не входит.
Может ли кто-нибудь помочь мне, если я использую неправильные функции? Я недавно узнал об этом, но я не могу найти информацию.
PD: я не говорящий по-английски, извините за мои грамматические и синтаксические проблемы.
Спасибо
// 10364 - Square.cpp: archivo de proyecto principal.
#include "stdafx.h"#include <stdio.h>
#include <vector>
using namespace std;
vector<int> vec;
int bitmask,casos,palitos,suma,maximo;
bool analiza(int analizado,int lados)// lados =cantidad lados analizados, contador
{
if (analizado==maximo)
{
analizado=0;
lados++;
}
if(lados==4)
{
printf("yes\n");
return true;
}
for (int i=0;i<palitos;i++)
{
if (!(bitmask & (1 << i)))
{
if (analizado+vec[i]<=maximo)
{
bitmask | (1 << i);
if(analiza(analizado+1,lados))
return true;
bitmask & ~(1 << i);
}
}
}
return false;
//prender: bitmask | (1 << indice)
//apagar: bitmask & ~(1 << indice)
/*comparar: bitmask & (1 << indice)*/
}
int main()
{
freopen("in.txt","rt",stdin);
freopen("out.txt","wt",stdout);
scanf("%d\n",&casos);
for(int i=0;i<casos;i++)
{
scanf("%d",&palitos);
vec.clear();
vec.resize(palitos);
suma=0;
for(int j=0;j<palitos;j++)
{
scanf("%d",&vec[j]);
suma+=vec[j];
}
if(suma%4!=0)
printf("no\n");
else{
bitmask=0;
maximo=suma/4;
analiza(0,0);
}}return 0;
}
Не похоже, что вы когда-либо инициализировали битовую маску. Если битовая маска равна 0, то вы никогда не войдете в цикл. Это кажется частью проблемы.
Также (bitmask & (1 << i)
можно упростить до «0», поскольку битовая маска равна 0, а вы используете побитовое и. Поэтому это целое условие может быть устранено, поскольку оно всегда будет оцениваться как истинное.
Кроме того, не похоже, что вы используете битовую маску в правильном направлении. Вы хотите, чтобы битовая маска имела хотя бы один из битов, равный единице. Таким образом, когда вы и какой-нибудь вектор с битовой маской, вы сохраните только соответствующий бит. Затем, если вы сдвигаете биты, вы можете определить, включен или выключен интересный бит в векторе.
Других решений пока нет …