uva 529 - Addition Chains
Addition Chains
An addition chain for n is an integer sequence with the following four properties:
You are given an integer n. Your job is to construct an addition chain for n with minimal length. If there is more than one such sequence, any one is acceptable.
For example, <1,2,3,5> and <1,2,4,5> are both valid solutions when you are asked for an addition chain for 5.
Input Specification
The input file will contain one or more test cases. Each test case consists of one line containing one integern ( ). Input is terminated by a value of zero (0) for
n.
Output Specification
For each test case, print one line containing the required integer sequence. Separate the numbers by one blank.Hint: The problem is a little time-critical, so use proper break conditions where necessary to reduce the search space.
Sample Input
5
7
12
15
77
0
Sample Output
1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77 dfs n=10000，17 ， ， ； 。 ， 。#include <string.h>
#include <stdio.h>
int a[100],best[100],n,min,f;
int minlen(int num,int len)
{int x=num,y=len;
while (x<n) {x=x<<1;++y;}
return y;
}
void dfs(int len)
{
int i,j,time,x;
if ((a[len]==n)&&(len<min)) {f=0; min=len; for (i=1;i<=len;i++) best[i]=a[i]; }
if ((a[len]>=n)||(len>=min)) return ;
if (minlen(a[len],len)>=min) return ;
for (i=1;i<=len;i++)
for (j=i;j<=len;j++)
{
a[len+1]=a[i]+a[j];
if (a[len+1]>a[len]) dfs(len+1);
}
}
int main()
{
int i;
a[1]=1; a[2]=2;
best[1]=1; best[2]=2;
while (scanf("%d",&n),n)
{
f=1; min=minlen(2,2)-1;
if (n<=2) {min=n;f=0;}
while (f)
{++min;
dfs(2);
}
for (i=1;i<min;i++)
printf("%d ",best[i]);
printf("%d
",n);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[Spring] properties 파일에 정의된 값 가져오기실시간 강의 수업 중 Admin key에 관련된 이야기가 나와 1,2차 Python, Flask 프로젝트에서 DB등 보완이 필요한 값들에 대해서 다른 곳에 따로 저장하고 변수에는 Path 설정해주고 github에 올...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
