[프로 그래 밍 의 아름다움] 2.8 조건 에 맞 는 정 수 를 찾 아 라.
17378 단어 프로 그래 밍 의 아름다움
나의 생각:
가장 낮은 자리 에서 가장 높 은 자리 까지 M 을 찾 아 매번 곱 하기 맨 뒤에 한 명 이 0, 1 의 조건 에 부합 하도록 한다.
그러면 끝자리 숫자 를 0 으로 만 들 수 있 는 예비 옵션 을 찾 아 보 세 요. 예 를 들 어 N 의 한 자릿수 가 9 이면... 뒤에서 오 는 진 위 를 고려 하여 x * 9 + c 의 끝 은 0 또는 1 입 니 다.
숫자 를 9 로 설정 하면 eligibleNum 에 저 장 된 숫자 eligibleNum [0] [0] = 0 은 9 * 0 + 0 = 0 끝 이 0 또는 1 eligibleNum [0] [0] = 9 는 9 * 9 + 0 = 81 끝 이 0 또는 1 eligibleNum [1] [0 = 0 은 9 * 1 + 1 = 10 끝 이 0 또는 1 eligibleNum [1] [1] = 1 은 9 * 0 + 1 = 1 끝 이 0 또는 1
...
이렇게 해서 모든 사람 을 판단 할 때 진위 c N 의 비트 숫자 만 알 면 조건 에 맞 는 예비 옵션 을 직접 찾 을 수 있 습 니 다.
그리고 광 도 를 우선 검색 하여 가장 작은 M 을 찾 습 니 다.
코드 중의 문제: 이 코드 는 풀 리 지 않 는 상황 을 판단 할 수 없고 답 의 자릿수 가 너무 많 을 때 진 위 를 잘못 판단 할 수 있 습 니 다. 기 존의 낮은 위치 와 관련 되 기 때문에 이 숫자 를 사용 해 야 하 는 곱셈 으로 인해 큰 수가 넘 칠 수 있 습 니 다.
아무튼 나 쁜 코드 야.유일 하 게 뿌 듯 한 게 우선 검색 을 연습 해 봤 어 요.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// n 0 1
bool IsAll01(int n)
{
while(n)
{
if((n % 10 == 0) || (n % 10 == 1))
{
n = n / 10;
}
else
{
return false;
}
}
return true;
}
/*
9 eligibleNum
eligibleNum[0][0] = 0 9 * 0 + 0 = 0 0 1
eligibleNum[0][0] = 9 9 * 9 + 0 = 81 0 1
eligibleNum[1][0] = 0 9 * 1 + 1 = 10 0 1
eligibleNum[1][1] = 1 9 * 0 + 1 = 1 0 1
...
*/
void getEligibleNum(int single, vector<vector<int>> * eligibleNum)
{
for(int i = 0; i < 10; i++) //
{
vector<int> tmp;
for(int j = 0; j < 2; j++) // 0、1
{
for(int k = 0; k < 10; k++)
{
int multi = k * 10 + j - i;
if((multi >= 0) && (multi % single == 0) && (multi/single < 10))
{
tmp.push_back(multi/single); //
}
else
{
continue;
}
}
}
eligibleNum->push_back(tmp);
}
}
////
void getAllAllowedAns(int N, vector<vector<int>> * eligibleNum,vector<vector<int>> * allAllowedAns, queue<vector<int>> Q)
{
bool isHaveAns = false; //
int currentLength = Q.front().size();
while(Q.front().size() == currentLength)
{
int addNum;
int alreadyNum = 0;
int pow = 1;
int currentMulti = 0;
if(currentLength == 0)
{
addNum = 0;
}
else
{
for(int i = currentLength - 1; i >= 0; i--)
{
alreadyNum = alreadyNum * 10 + Q.front()[i];
pow *= 10;
}
currentMulti = alreadyNum * N;
addNum = (currentMulti / pow ) % 10;
}
vector<int>::iterator it;
for(it = (*eligibleNum)[addNum].begin(); it < (*eligibleNum)[addNum].end(); it++) //
{
vector<int> currentAns = Q.front();
currentAns.push_back(*it);
if(IsAll01((*it) * N + currentMulti / pow)) //
{
allAllowedAns->push_back(currentAns);
isHaveAns = true;
}
else
{
Q.push(currentAns);
}
currentAns.pop_back();
}
Q.pop();
}
if(isHaveAns == true && currentLength != 0)
{
return;
}
else
{
getAllAllowedAns(N, eligibleNum, allAllowedAns, Q);
}
}
char * getSmallestM(int N)
{
vector<vector<int>> eligibleNum; //
vector<vector<int>> allAllowedAns;
vector<int> tmpAns;
queue<vector<int>> Q;
Q.push(tmpAns);
int single; // N
while(N % 10 == 0) //N 0
N = N / 10;
single = N % 10;
getEligibleNum(single, &eligibleNum);
getAllAllowedAns(N, &eligibleNum, &allAllowedAns, Q);
return NULL;
}
int main()
{
getSmallestM(35);
return 0;
}아래 의 높 고 큰 답안:
답 은 M 을 생각 하지 않 고 M * N 을 찾 는 것 부터 시작한다.M * N 은 0 과 1 만 표시 하 는 것 이 더 간편 하기 때문이다.
하나의 벡터 로 X% N = i 의 모든 i 상황 에서 가장 작은 X 를 저장 합 니 다.
10 ^ k + Y 와 의 상황
먼저 계산 j = 10^k % N
그리고 (j + 기 존 나머지)% N 으로 새로운 나머지 가 생기 면 저장 합 니 다.
또한 100% N = (10% N) * 10% N 은 이러한 규칙 을 이용 하여 10 ^ k 의 대수 표 시 를 피 할 수 있다.
이 경우 N 개 공간의 나머지 벡터 를 유지 하기 만 하면 모든 요 소 는 일정 하지 않 은 배열 이 고 M * N 을 저장 하 는 몇 번 째 위 는 1 이 며 대수 적 표현 도 피 할 수 있다.
그리고 옮 겨 다 니 는 시간 이 적 습 니 다. 마지막 답 이 K 자리 가 있다 면 한 명 씩 N 번 만 옮 겨 다 니 면 됩 니 다. 결국 옮 겨 다 니 면 됩 니 다 (K - 1) * N 걸음 이 빠 릅 니 다.
코드: BigInt [0] 는 가장 작은 M * N 의 값 입 니 다.
#include <iostream>
#include <vector>
using namespace std;
typedef unsigned char uchar;
//BigInt M * N 1
void GetSmallestM(int N, vector<vector<uchar>> * BigInt)
{
int i , j;
vector<uchar> init;
init.clear();
//
for(i = 0; i < N; i++)
{
BigInt->push_back(init);
}
(*BigInt)[1].push_back(0); // 1 1 0 1
int NoUpdate = 0;
//i 10^i j 10^i % N 100 % N = ((10 % N) * 10) % N j
for(i = 1, j = 10 % N; ; i++, j = (j * 10) % N)
{
bool flag = false;
//
if((*BigInt)[j].size() == 0)
{
flag = true;
(*BigInt)[j].clear();
(*BigInt)[j].push_back(i);
}
// (j + k) % N
for(int k = 1; k < N; k++)
{
if((*BigInt)[j].size() > 0 &&
((*BigInt)[k].size() > 0 && i > (*BigInt)[k][(*BigInt)[k].size() - 1]) // i k BigInt
&& (*BigInt)[(k + j) % N].size() == 0)
{
flag = true;
(*BigInt)[(k + j) % N] = (*BigInt)[k];
(*BigInt)[(k + j) % N].push_back(i);
}
}
if(flag == false)
NoUpdate++;
else
NoUpdate = 0;
// N N N
//
if(NoUpdate == N || (*BigInt)[0].size() > 0)
break;
}
if((*BigInt)[0].size() == 0)
{
cout << "M not exist" << endl;
}
else
{
return;
}
}
int main()
{
vector<vector<uchar>> BigInt;
GetSmallestM(99, &BigInt);
return 0;
}좋은 웹페이지 즐겨찾기
