算法：用5,7,12加减运算，求最少步数得到任意数n解决办法

算法：用5,7,12加减运算，求最少步数得到任意数n
rt

[解决办法]
O(1)时间复杂度。

C/C++ code

/*** 用5,7,12加减运算，最少步骤到大n* gogdizzy@gmail.com*/#include <stdio.h>#define abs(x) \    ( (x^(x>>31))-(x>>31) )int min_step( int N ){    int diff;    int n5, n7, n12;    int r5, r7, r12;    unsigned tmp, total = unsigned (-1); // assign a very big num        for( n5 = -6; n5 < 7; ++n5 )    {        diff = N - 5 * n5;        n7 = diff / 7;        n12 = diff / 12;        if( 12 * n12 + 5 * n5 == N )        {            tmp = abs( n5 ) + abs( n12 );            if( total > tmp ) r5 = n5, r7 = 0, r12 = n12, total = tmp;        }        else if( 7 * n7 + 5 * n5 == N )        {            if( n7 > -12 && n7 < 12 )            {                tmp = abs( n5 ) + abs( n7 );                if( total > tmp ) r5 = n5, r7 = n7, r12 = 0, total = tmp;            }        }    }    for( n7 = -11; n7 < 12; ++n7 )    {        n12 = ( N - 7 * n7 ) / 12;        if( 7 * n7 + 12 * n12 == N )        {            tmp = abs( n7 ) + abs( n12 );            if( total > tmp ) r5 = 0, r7 = n7, r12 = n12, total = tmp;        }    }    printf( "%d = (%d) * 5 + (%d) * 7 + (%d) * 12\ntotal:%d\n", N, r5, r7, r12, total );    return total;}int main(){    int n;    scanf( "%d", &n );    min_step( n );    return 0;}
[解决办法]
引用 lisunlin0 的博客:

有同学面试的时候遇到要求一个数以最少步骤分解为另外两个数和差问题的解决，大约描述是“将一个数分解为几个数的和或者差的形式，并且使步骤最小”。

这类题的解题理论是数论里面的一次不定方程的整数解。
引用 百度百科:
定义1. 形如 ax + by = c ( a，b，c∈Z，a，b不同时为零)的方程称为二元一次不定方程。
定理1. 方程 ax + by = c 有解的充要是 ( a,b ) | c；
定理2. 若( a,b ) = 1，且 x_0，y_0为 ax + by = c 的一个解，则方程的一切解都可以表示成
 x=x0+t*b/(a,b)
 y=y0+t*a/(a,b)

定理3. n元一次不定方程 a_1x_1 + a_2x_2 +…+ a_nx_n = c，( a_1，a_2，…a_n，c∈N )有解的充要条件是：( a_1，a_2，…a_n ) | c.


例如将任意数分解５和７的和差形式，求最少需要多少次可以完成。
转换成数学描述就是求解
5a+7b=A
的整数解 a=a0+Xm, b=b0+Ym, 并且使|a0|+|b0|最小。
以求解123分解为５和７的组合为例：
１、5和７的最大公约数(5,7)是１,可以运算
２、使用辗转相除法
5a+7b=123,
a=(123-7b)/5 = 25-b-2(1+b)/5　令(1+b)/5=m得
b=-1+5m, a=25-(-1+5m)-2m = 26-7m
下面求最小的|a|+|b|.

m<=1/5或者m>=26/7时min(|a|+|b|)=min(|a-b|)=min(|27-12m|)取m整数值m=4,得min(|a|+|b|)=21

1/5<= m <=26/7时min(|a|+|b|) = min(a+b)=min(25-2m)取m=3得min(|a|+|b|)=19

可见取m=3时可得最小步骤为19次和差运算，且a=5,b=14