Additive sequence algorithm

Question

Additive sequence algorithm

Ex: 1235 (split it 1,2,3,5) Ex: 12122436(split 12,12,24,36) given range find all additive seq numbers?

Below I tried, I know that it is not effective and not sure of its complexity. In addition, he does not find numbers like 53811 and 12122436 that interest me. I will be very grateful if someone can lead me in the right direction or come up with something simpler and more efficient. Thanks!

 #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; } }

+6

c algorithm numbers logic sequences

Vbp Nov 12 '13 at 1:37

source share

2 answers

גלעד ברקן · Answer 1 · 2013-11-12T23:02:49+0000

I'm not sure how effective this would be, but I could try something recursive.

For example, 53811

Indicate, for example, the end of the line.

 Var2 = 1 Var1 = 1

Check if Var0 Var2 - Var1

1 - 1 not equal to 8 , so this function chain ends.

In the next function chain, Var2 is equal to the last two digits, 11 ; Var1 = 8

Check if Var0 Var2 - Var1

11 - 8 is 3 , so this function chain continues: Var2 = 8 ; Var1 = 3

Check if Var0 Var2 - Var1

8 - 3 equals 5 , and this is also the end of the line, so the function returns True

The basic example, apparently, is that the pointer is at the beginning of the line or viable variables cannot be checked. At each connection point, Var2 and Var1 would be changed respectively to start a new chain; Var0 is derived from the other two.

jeffrey · Answer 2 · 2013-11-12T05:35:37+0000

Suppose the length of the original sequence is n. An obvious approach that can work is to roughly list the lengths of the first and second elements and check if it is correct in linear time. This approach takes O(n ^ 3) .

You claim that your approach takes O(n) , but from your implementation, I suspect that your n denotes the length of the original sequence.

Additive sequence algorithm

More articles: