我正在练习面试算法,并在Career Cup和SO上发现了这个问题。
加性数列是指当分解成两个不同的数字形式时为加性数列。
例如:1235(拆分为1、2、3、5)
例如:12122436(拆分为12、12、24、36)
给定一个范围,找出所有的加性数列?
以下是我尝试过的内容,我知道它不够高效,也不确定它的复杂度。此外,它不能找到像53811和12122436这样的数字,这正是我感兴趣的。如果有人能指导我正确方向或想出更简单有效的方法,我将非常感激。谢谢!
例如:1235(拆分为1、2、3、5)
例如:12122436(拆分为12、12、24、36)
给定一个范围,找出所有的加性数列?
以下是我尝试过的内容,我知道它不够高效,也不确定它的复杂度。此外,它不能找到像53811和12122436这样的数字,这正是我感兴趣的。如果有人能指导我正确方向或想出更简单有效的方法,我将非常感激。谢谢!
#include <stdio.h>
void check_two_num_sum(int,int);
void check_sum(int);
int flag = 0;
int main(){
int high,low;
printf("Enter higher range\n");
scanf("%d",&high);
printf("Enter lower range\n");
scanf("%d",&low);
check_two_num_sum(high,low);
return 0;
}
void check_two_num_sum(int high, int low)
{
flag=0;
for(low;low<high;low++)
{
check_sum(low);
if(flag==1)
{
printf("this value has additive sequence %d \n",low);
flag = 0;
}
}
}
void check_sum(int input)
{
int count = 1;
int capture, result, temp_res=0, n=0;
if(n==0){
result = input%10;
n++;
input = input/10;
capture = input;
}
while(input!=0)
{
temp_res = temp_res + input%10;
if(count ==2)
{
if(result == temp_res)
{
if(capture < 100)
{ flag = 1;
break;
}
else{
check_sum(capture);
}
}
else {
break;
}
}
count++;
input = input/10;
}
}