동적 계획 의 최대 K 곱 하기 문제
3683 단어 실험 하 다.
설정 I 는 n 비트 10 진수 입 니 다.I 를 k 단 으로 나 누 면 k 개의 정 수 를 얻 을 수 있다.이 k 개의 정수 곱 하기 를 I 의 k 곱 하기 라 고 한다.주어진 I 와 k 에 대해 I 의 최대 k 곱 하기 알고리즘 을 시험 적 으로 설계 합 니 다.예 를 들 어 십 진법 정수 1234 를 3 단 으로 나 누 면 다음 과 같은 상황 이 있 을 수 있다.× 2 × 34 = 68 1 × 23 × 4 = 92 12 × 3 × 4 = 144
대체적인 사고 방식.
최 우수 원 리 를 만족 시 키 는 것 을 증명 한다. 가설 최대 k 곱 하기 는 앞의 x 위 를 k - 1 단 으로 나 누고 마지막 정 수 를 곱 하 는 것 이다.만약 에 앞의 x 위의 구분 이 가장 좋 은 방법 이 아니라면 그 곱 은 반드시 최 적 화 된 방법 으로 얻 은 곱 하기 S 보다 작 을 것 이다.max 는 마지막 정수 소득 결과 와 최대 k 곱 하기 가 아니 라 전제 와 모순 된다.따라서 앞의 x 위 를 k - 1 단 소득 결과 비 로 나 누 어 최대 곱 하기 로 한다.[동적 계획 문제 에서 최 우수 원리 에 대한 증명 은 주로 반증 법 을 사용한다] 동적 계획 함수 령 number (i, j) 를 확정 하면 i 위 에서 j 위 정수 로 구 성 된 (j - i + 1) 비트 정 수 를 나타 낸다.produt (p, q) 은 앞 p 비트 정수 가 q 세그먼트 로 나 뉘 어 얻 은 최대 곱 하기 임 을 나타 낸다.[구분 단수 가 정수 자리수 보다 크 면 결 과 는 0]
초기 하위 문제: (q = 1 시) produt (p, 1) = number (1, p) 는 몇 개의 정수 에 관 계 없 이 한 단락 으로 나 뉘 어 있 으 며, 최대 k 곱 하기 는 모두 그 자체 입 니 다.다음 단계 의 문제: (q > 1 및 q < = p 시) product (p, q) = max {product (x, q - 1) * number (x + 1, p)} (1 < = x < = p - 1) p 는 정수 로 q 단 으로 나 뉘 어 각각 앞의 x 비트 이 수 를 q - 1 단 소득 의 최대 곱 하기 와 나머지 세그먼트 의 곱 하기 로 나 누 어 적당 한 데이터 구조 기록 을 선택 한 다음 비교 하면 가장 큰 결 과 는 produt (p, q) 이다.
리스트
q\p
1
2
3
4
1
1
12
123
1234
2
0
2
36
492
3
0
0
6
144
4
0
0
0
24
첫 번 째 줄 은 정 수 를 한 단락 으로 나 누고 결 과 는 그 자체 이다.두 번 째 줄 product (2, 2) = max {product (1, 1) * number (2, 2)} = 2;product(3,2)=max{product(1,1)*number(2,3), product(2,1)*number(3,3)}=max{1*23,12*3}=36; product(4,2)=max{product(1,1)*number(2,4),product(2,1)*number(3,4),product(3,1)*number(4,4)}=max{1*234,12*34,123*4}=492; 세 번 째 줄 product (3, 3) = max {product (2, 2) * number (3, 3)} = 6;product(4,3)=max{product(3,2)*number(4,4),product(2,2)*number(3,4)}=max{36*4,2*34}=144; 네 번 째 줄 product (4, 4) = max {product (3, 3) * number (4, 4)} = 24;
q\p
3
31
312
1
3
31
312
2
0
3
62
c + + 소스 코드 구현
#include
#include
using namespace std;
// n k
//
void getnumber(int number[20],int num,int n)
{
int b = 0;
for (int a = n-1; a>=0; a--)
{
b = num % 10;
num = num / 10;
number[a] = b;
}
return;
}
// p q
int countnumber(int p, int q,int *number)
{
int newnumber = 0;
for (int a=p;a<=q;a++)
{
newnumber = newnumber* 10+number[a];
}
return newnumber;
}
int main()
{
int k; int n; int num;
int number[20];
int product[20][20];
ifstream f1("C:\\Data\\1.txt");
ofstream f2("C:\\Data\\2.txt");
f1 >> n;
f1 >> k;
f1 >> num;
getnumber(number, num, n);
if (k == 1)//
{
cout << " k " << num << "
";
f2 << " k " << num << "
";
return 0;
}
for (int temp = 0; temp < n; temp++)
{
product[0][temp] = countnumber(0, temp, number);
}
for (int i = 0; i < n; i++)//i
{
for (int j = 1; j < k; j++)//j
{
if (j > i)
{
product[j][i] = 0;
break;//
}
if (j <= i)
{
int max = 0; int temp = 0;
for (int a = i-1; a >= 0; a--)
{
int nnum = countnumber(a + 1, i, number);
temp = nnum * product[j - 1][a];
if (temp > max)
max = temp;//
}
product[j][i] = max;
}
}
}
cout << " k " << product[k-1][n-1] << "
";
f2 << " k " << product[k - 1][n - 1] << "
";
f1.close();
f2.close();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
남 우편 데이터 구조 실험 1 순서 표 조작실험 내용 과 힌트: 1. 순서 표 클래스 SeqList 에 구성원 함수 void Reverse () 를 추가 하여 순서 표 의 역 치 를 실현 합 니 다. 2. 순서 표 클래스 SeqList 에 구성원 함수 boo...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.