精华内容
下载资源
问答
  • 用递归代替循环嵌套算法思想

    千次阅读 2019-05-08 11:54:16
    问题引入:输出2位数字的所有排列组合 ...for(int i = 0;i<10;i++){ for(int j = 0;j<10;j++){ System.out.println(i+""+j); } } 那要是输出3位数字的排列组合呢?你可能会想那就多套一层循...

    问题引入:输出2位数字的所有排列组合

    对于这个问题我们很快可以想出解决方案:

    for(int i = 0;i<10;i++){
               for(int j = 0;j<10;j++){
                   System.out.println(i+""+j);
               }
           }
    

    那要是输出3位数字的排列组合呢?你可能会想那就多套一层循环咯:

    for(int i = 0;i<10;i++){
               for(int j = 0;j<10;j++){
                   for(int k = 0;k<10;k++){
                       System.out.println(i+""+j);
                   }
               }
           }
    

    但是现在问题来了,假如题目的要求是给定一个n整数,要求你输出n位数的排列组合呢,这时上面的循环做法就没办法解决了,因为你不知道要套多少层,你不知道要写多少次for循环。

    这时候就需要通过递归来代替循环了:
    函数传入参:当前循环位置cur,一共循环需要的次数n,前面的循环所得的子输出str

    class Solution {
    
       public static void main(String[] args){
           new Solution().show(0,5,"");
       }
       
        void show(int cur,int n,String str){
        //循环位置到达最后,输出字符串
            if (cur==n) System.out.println(str);
            else{
                for(int i = 0;i<10;i++){
                    String s = str+i;
                    show(cur+1,n,s);
                }
            }
        }
    }
    

    这种递归代替嵌套循环的思想在不少算法题体现过:
    1 《剑指offer》字符串的排列
    (解析:https://blog.csdn.net/qq_42862882/article/details/89410321)

    2 leetCode 17题. 电话号码的字母组合

    展开全文
  • 基础算法思想

    千次阅读 2013-09-29 01:26:29
    算法设计的任务就是:针对一个具体的问题,利用特定的方法和步骤来获取最佳结果。 1.编程的灵魂:算法+数据结果  刚开始学编程的人总是会陷入这样的误区,以为学会了一门语言就学会了编程,总会学各种各样的语言。...

            算法设计的任务就是:针对一个具体的问题,利用特定的方法和步骤来获取最佳结果。

    编程的灵魂:算法+数据结构

          刚开始学编程的人总是会陷入这样的误区,以为学会了一门语言就学会了编程,总会学各种各样的语言。实际上,语言只是一个工具,解决具体的问题必须依赖于算法,而算法从本质上讲是数学方法的表达。通过一定的数学知识来解答。一个好的系统分析师或设计师,或许他们可以不会任何一种语言,但如果他们能通过数学公式或图形等准确的表达出解决问题的方法和步骤,他们照样可以成为这个行业的佼佼者,拿高工资。

          一个算法的5个重要特征:

          *有穷性:一个算法必须在有穷步之后结束,且每一步必须在有穷的时间内完成。

          *确定性:算法中的每一条指令必须有确切的含义,不能产生二义性。在任何条件下,算法只有唯一的一条执行路径,即对于相同的输入只能得出相同的输出。

          *可行性:一个算法必须是可行的,即算法中的操作都必须通过已实现的基本运算执行有限次来实现。

          *输入:一个算法可以有0个或多个输入。

          *输出:一个算法必须有1个或多个输出。

          算法设计要求:正确性、可读性、健壮性、高效率低地存储

    1.迭代思想:

         迭代法和递推法类似,也是递增求解,不同的是:在递推法中,每一步得到的解是相对于对应问题规模的完整解;在迭代法中,中间步骤得到的解一般只是“近似解”,并不代表问题的解。

        看一道迭代法的应用例子:求解一个数的开方。√¯a;

        分析:设√¯a = x,则 x2 - 1 = a -1

                   变换得: (x-1)(x+1) = a - 1

                         x = 1 + (a-1)/(1+x)  ~~~~~~~这就是迭代公式

    程序实现:

    #include <stdio.h>
    #include <MATH.H>
    
    #define epsilon 1e-10
    
    float Sqrt(float a)
    {
    	float x,x0;
    	x = 1;
    	do{
    		x0 = x;
    		x = 1 + (a-1)/(x+1);
    	}while(fabs(x-x0) > epsilon);
    
    	return x;
    }
    void main()
    {
    	float num;
    	float result1;
    	float result2;
    
    	printf("请输入一个浮点数:");
    	scanf("%f",&num);
    
    	result1 = Sqrt(num);
    	result2 = (float)sqrt(num);
    	printf("库函数的计算结果:%f\n自己编写的函数计算结果%f\n",result2,result1);
    }


    关于更多迭代法的使用,可参见我的博客《编写自己的Math函数库

    2.地推思想:

       从已知条件出发,利用特定的关系得出中间推论,逐步递推,直至得到结果为止。

    1)顺推法

       所谓顺推法,就是从已知条件出发,逐步推算出要解决问题的方法。例如:斐波那契数。

    算法实现:

    #include <stdio.h>
    #define NUM 13
    
    void main()
    {
        int i;
        long fib[NUM] = {1,1};
        for(i = 2; i < NUM; i++)
        {
            fib[i] = fib[i-1] + fib[i-2];
        }
        for(i = 0; i < NUM; i++)
        {
            printf("%d\n",fib[i]);
        }
    }

     

    2)逆推法

       所谓逆推法,就是从已知的结果出发,用迭代表达式逐步推算出问题开始的条件。例如:

       父亲准备为小龙的4年大学生活一次性在银行存一笔钱,使用整存零取的方式,控制小龙每月月底只能取1000元准备下一个月使用。假设银行一年整存零取的利率为1.71%,请编程实现父亲至少一次性存入多少钱才够小龙4年的生活费。

    #include "stdio.h"
    #define FETCH 1000
    #define RATE 0.0171
    
    void main()
    {
    	double corpus[49];
    	int i;
    	corpus[48] = (double)FETCH;
    	for(i = 47;i > 0; i--)
    	{
    		corpus[i] = (corpus[i+1]+FETCH)/(1+RATE/12);
    	}
    	for(i = 48; i > 0; i--)
    	{
    		printf("第%d月末本利合计:%.2f\n",i,corpus[i]);
    	}
    }
    

    3.穷举算法思想:

      计算机最大的优势就是遍历和循环,一些人工计算很麻烦的问题,利用计算机穷举法就可以很好地解决。例如:百钱买鸡。

    #include "stdio.h"
    void BuyChicken()
    {
    	int x,y,z;
    	for(x = 0; x <= 20; x++)
    	{
    		for(y = 0; y <= 33; y++)
    		{
    			z = 100 - x - y;
    			if(z % 3 == 0 && x*5 + y*3 + z/3 == 100)
    			{
    				printf("公鸡:%d,母鸡:%d,小鸡:%d\n",x,y,z);
    			}
    		}
    	}
    }
    void main()
    {
    	BuyChicken();
    }
    
    

    算法实现:

    4.递归算法思想:

            递归算法的思想就是通过对问题的分解,使其能够分解为与原问题相似的子问题的过程,最后得出结果。例如:求阶乘、汉诺塔等。

    求阶乘算法实现:

    int fact(int n)
    {
    	if(n <= 1)
    	{
    		return 1;
    	}
    	else
    	{
    		return n*fact(n-1);
    	}
    }

    5.分治算法思想:

       对于一个规模为n的问题,若该问题可以很容易的解决,则直接解决,否则将其分解为M个规模较小的子问题,这些子问题相互独立,并且与原问题有相同的形式。

    6.贪婪算法思想:

       贪婪算法是一种不追求最优解,只希望得到较为满意的方法。例如:换零钱。

    7.回溯算法思想:

       也称试探法,基本思想:为了求解问题的解,先选择某一种试探,在试探过程中,一但发现以前的选择假设有错误,则会退到上一步,如此反复进行,直至得到最终解。

    例如:迷宫问题。

    8.模拟算法:

       通过计算机来模拟对应的一些数学模型。例如:模拟随机抛硬币的结果。

    9.动态规划:

       基本思想是将大问题分解乘小问题,为了节约重复求解子问题的时间,引入一个数组,不管他们是否对最终解有用,把所有子问题的解保存在该数组中,这就是动态规划所采用的基本思想。

    算法的评价:

    1)时间复杂度:通过统计算法中基本操作重复执行的次数来近似的得到算法的执行效率,用O(n)表示。

       常见的渐近时间复杂度效率比较:

       O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n)

    2)空间复杂度:程序在运行过程中所需占用的最大内存空间。

    3)程序的可读性:程序的可读性有时比高效性更重要,因为可读性增强,易于调试和维护。

    展开全文
  • 三角函数计算,Cordic 算法入门

    万次阅读 多人点赞 2013-01-02 13:47:45
    三角函数计算,Cordic 算法入门 三角函数的计算是个复杂的主题,有计算机之前,人们通常通过查找三角函数表来计算任意角度的三角函数的值。这种表格在人们刚刚产生三角函数的概念的时候就已经有了,它们通常是通过...

    三角函数计算,Cordic 算法入门

    三角函数的计算是个复杂的主题,有计算机之前,人们通常通过查找三角函数表来计算任意角度的三角函数的值。这种表格在人们刚刚产生三角函数的概念的时候就已经有了,它们通常是通过从已知值(比如sin(π/2)=1)开始并重复应用半角和和差公式而生成。

    现在有了计算机,三角函数表便推出了历史的舞台。但是像我这样的喜欢刨根问底的人,不禁要问计算机又是如何计算三角函数值的呢。最容易想到的办法就是利用级数展开,比如泰勒级数来逼近三角函数,只要项数取得足够多就能以任意的精度来逼近函数值。除了泰勒级数逼近之外,还有其他许多的逼近方法,比如切比雪夫逼近、最佳一致逼近和Padé逼近等。

    所有这些逼近方法本质上都是用多项式函数来近似我们要计算的三角函数,计算过程中必然要涉及到大量的浮点运算。在缺乏硬件乘法器的简单设备上(比如没有浮点运算单元的单片机),用这些方法来计算三角函数会非常的费时。为了解决这个问题,J. Volder1959年提出了一种快速算法,称之为CORDIC(COordinate Rotation DIgital Computer) 算法,这个算法只利用移位和加减运算,就能计算常用三角函数值,如SinCosSinhCosh等函数。 J. Walther1974在这种算法的基础上进一步改进,使其可以计算出多种超越函数,更大的扩展了Cordic 算法的应用。因为Cordic 算法只用了移位和加法,很容易用纯硬件来实现,因此我们常能在FPGA运算平台上见到它的身影。不过,大多数的软件程序员们都没有听说过这种算法,也更不会主动的去用这种算法。其实,在嵌入式软件开发,尤其是在没有浮点运算指令的嵌入式平台(比如定点型DSP)上做开发时,还是会遇上可以用到Cordic 算法的情况的,所以掌握基本的Cordic算法还是有用的。


    从二分查找法说起

    先从一个例子说起,知道平面上一点在直角坐标系下的坐标(X,Y=100200),如何求的在极坐标系下的坐标(ρ,θ)。用计算器计算一下可知答案是(223.6163.435)。



    图 1 直角坐标系到极坐标系的转换

    为了突出重点,这里我们只讨论XY都为正数的情况。这时θ=atan(y/x)。求θ的过程也就是求atan 函数的过程。Cordic算法采用的想法很直接,将(XY)旋转一定的度数,如果旋转完纵坐标变为了0,那么旋转的度数就是θ。坐标旋转的公式可能大家都忘了,这里把公式列出了。设(x,y)是原始坐标点,将其以原点为中心,顺时针旋转θ之后的坐标记为(x’,y’),则有如下公式:


    也可以写为矩阵形式:


    如何旋转呢,可以借鉴二分查找法的思想。我们知道θ的范围是0到90度。那么就先旋转45度试试。


    旋转之后纵坐标为70.71,还是大于0,说明旋转的度数不够,接着再旋转22.5度(45度的一半)。


    这时总共旋转了45+22.5=67.5度。结果纵坐标变为了负数,说明θ<67.5度,这时就要往回转,还是二分查找法的思想,这次转11.25度。

    这时总共旋转了45+22.5-11.25=56.25度。又转过头了,接着旋转,这次顺时针转5.625度。

    这时总共旋转了45+22.5-11.25+5.625=61.875度。这时纵坐标已经很接近0了。我们只是说明算法的思想,因此就不接着往下计算了。计算到这里我们给的答案是 61.875±5.625。二分查找法本质上查找的是一个区间,因此我们给出的是θ值的一个范围。同时,坐标到原点的距离ρ也求出来了,ρ=223.52。与标准答案比较一下计算的结果还是可以的。旋转的过程图示如下。

    可能有读者会问,计算中用到了 sin 函数和 cos 函数,这些值又是怎么计算呢。很简单,我们只用到很少的几个特殊点的sin 函数和 cos 函数的值,提前计算好存起来,用时查表。

    下面给出上面方法的C 语言实现。

    #include <stdio.h>
    #include <stdlib.h>
    
    double my_atan2(double x, double y);
    int main(void)
    {
        double z = my_atan2(100.0, 200.0);
        printf("\n z = %f \n", z);
    
        return 0;
    }
    
    
    double my_atan2(double x, double y)
    {
        const double sine[] = {0.7071067811865,0.3826834323651,0.1950903220161,0.09801714032956,
    0.04906767432742,0.02454122852291,0.01227153828572,0.006135884649154,0.003067956762966
    ,0.001533980186285,7.669903187427045e-4,3.834951875713956e-4,1.917475973107033e-4,
    9.587379909597735e-5,4.793689960306688e-5,2.396844980841822e-5
                             };
    
        const double cosine[] = {0.7071067811865,0.9238795325113,0.9807852804032,0.9951847266722,
    0.9987954562052,0.9996988186962,0.9999247018391,0.9999811752826,0.9999952938096,
    0.9999988234517,0.9999997058629,0.9999999264657,0.9999999816164,0.9999999954041,
    0.999999998851,0.9999999997128
                               };
    
    
        int i = 0;
        double x_new, y_new;
        double angleSum = 0.0;
        double angle = 45.0;
    
        for(i = 0; i < 15; i++)
        {
            if(y > 0)
            {
                x_new = x * cosine[i] + y * sine[i];
                y_new = y * cosine[i] - x * sine[i];
                x = x_new;
                y = y_new;
                angleSum += angle;
            }
            else
            {
                x_new = x * cosine[i] - y * sine[i];
                y_new = y * cosine[i] + x * sine[i];
                x = x_new;
                y = y_new;
                angleSum -= angle;
            }
            printf("Debug: i = %d angleSum = %f, angle = %f\n", i, angleSum, angle);
            angle /= 2;
        }
        return angleSum;
    }

    程序运行的输出结果如下:

    Debug: i = 0 angleSum = 45.000000, angle = 45.000000
    Debug: i = 1 angleSum = 67.500000, angle = 22.500000
    Debug: i = 2 angleSum = 56.250000, angle = 11.250000
    Debug: i = 3 angleSum = 61.875000, angle = 5.625000
    Debug: i = 4 angleSum = 64.687500, angle = 2.812500
    Debug: i = 5 angleSum = 63.281250, angle = 1.406250
    Debug: i = 6 angleSum = 63.984375, angle = 0.703125
    Debug: i = 7 angleSum = 63.632813, angle = 0.351563
    Debug: i = 8 angleSum = 63.457031, angle = 0.175781
    Debug: i = 9 angleSum = 63.369141, angle = 0.087891
    Debug: i = 10 angleSum = 63.413086, angle = 0.043945
    Debug: i = 11 angleSum = 63.435059, angle = 0.021973
    Debug: i = 12 angleSum = 63.424072, angle = 0.010986
    Debug: i = 13 angleSum = 63.429565, angle = 0.005493
    Debug: i = 14 angleSum = 63.432312, angle = 0.002747
    
     z = 63.432312

    减少乘法运算

    现在已经有点 Cordic 算法的样子了,但是我们看到没次循环都要计算 4 次浮点数的乘法运算,运算量还是太大了。还需要进一步的改进。改进的切入点当然还是坐标变换的过程。我们将坐标变换公式变一下形。

    可以看出 cos(θ)可以从矩阵运算中提出来。我们可以做的再彻底些,直接把 cos(θ) 给省略掉。

    省略cos(θ)后发生了什么呢,每次旋转后的新坐标点到原点的距离都变长了,放缩的系数是1/cos(θ)。不过没有关系,我们求的是θ,不关心ρ的改变。这样的变形非常的简单,但是每次循环的运算量一下就从4次乘法降到了2次乘法了。

    还是给出 C 语言的实现:

    double my_atan3(double x, double y)
    {
        const double tangent[] = {1.0,0.4142135623731,0.1989123673797,0.09849140335716,0.04912684976947,
    0.02454862210893,0.01227246237957,0.006136000157623,0.003067971201423,
    0.001533981991089,7.669905443430926e-4,3.83495215771441e-4,1.917476008357089e-4,
    9.587379953660303e-5,4.79368996581451e-5,2.3968449815303e-5
                             };
    
    
        int i = 0;
        double x_new, y_new;
        double angleSum = 0.0;
        double angle = 45.0;
    
        for(i = 0; i < 15; i++)
        {
            if(y > 0)
            {
                x_new = x + y * tangent[i];
                y_new = y - x * tangent[i];
                x = x_new;
                y = y_new;
                angleSum += angle;
            }
            else
            {
                x_new = x - y * tangent[i];
                y_new = y + x * tangent[i];
                x = x_new;
                y = y_new;
                angleSum -= angle;
            }
            printf("Debug: i = %d angleSum = %f, angle = %f, ρ = %f\n", i, angleSum, angle, hypot(x,y));
            angle /= 2;
        }
        return angleSum;
    }

    计算的结果是:

    Debug: i = 0 angleSum = 45.000000, angle = 45.000000, ρ = 316.227766
    Debug: i = 1 angleSum = 67.500000, angle = 22.500000, ρ = 342.282467
    Debug: i = 2 angleSum = 56.250000, angle = 11.250000, ρ = 348.988177
    Debug: i = 3 angleSum = 61.875000, angle = 5.625000, ρ = 350.676782
    Debug: i = 4 angleSum = 64.687500, angle = 2.812500, ρ = 351.099697
    Debug: i = 5 angleSum = 63.281250, angle = 1.406250, ρ = 351.205473
    Debug: i = 6 angleSum = 63.984375, angle = 0.703125, ρ = 351.231921
    Debug: i = 7 angleSum = 63.632813, angle = 0.351563, ρ = 351.238533
    Debug: i = 8 angleSum = 63.457031, angle = 0.175781, ρ = 351.240186
    Debug: i = 9 angleSum = 63.369141, angle = 0.087891, ρ = 351.240599
    Debug: i = 10 angleSum = 63.413086, angle = 0.043945, ρ = 351.240702
    Debug: i = 11 angleSum = 63.435059, angle = 0.021973, ρ = 351.240728
    Debug: i = 12 angleSum = 63.424072, angle = 0.010986, ρ = 351.240734
    Debug: i = 13 angleSum = 63.429565, angle = 0.005493, ρ = 351.240736
    Debug: i = 14 angleSum = 63.432312, angle = 0.002747, ρ = 351.240736
    
     z = 63.432312

    消除乘法运算

    我们已经成功的将乘法的次数减少了一半,还有没有可能进一步降低运算量呢?还要从计算式入手。

    第一次循环时,tan(45)=1,所以第一次循环实际上是不需要乘法运算的。第二次运算呢?

    Tan(22.5)=0.4142135623731,很不幸,第二次循环乘数是个很不整的小数。是否能对其改造一下呢?答案是肯定的。第二次选择22.5度是因为二分查找法的查找效率最高。如果选用个在22.5到45度之间的值,查找的效率会降低一些。如果稍微降低一点查找的效率能让我们有效的减少乘法的次数,使最终的计算速度提高了,那么这种改进就是值得的。

    我们发现tan(26.565051177078)=0.5,如果我们第二次旋转采用26.565051177078度,那么乘数变为0.5,如果我们采用定点数运算的话(没有浮点协处理器时为了加速计算我们会大量的采用定点数算法)乘以0.5就相当于将乘数右移一位。右移运算是很快的,这样第二次循环中的乘法运算也被消除了。

    类似的方法,第三次循环中不用11.25度,而采用 14.0362434679265 度。

    Tan(14.0362434679265)= 1/4

    乘数右移两位就可以了。剩下的都以此类推。

    tan(45)= 1
    tan(26.565051177078)= 1/2
    tan(14.0362434679265)= 1/4
    tan(7.1250163489018)= 1/8
    tan(3.57633437499735)= 1/16
    tan(1.78991060824607)= 1/32
    tan(0.8951737102111)= 1/64
    tan(0.4476141708606)= 1/128
    tan(0.2238105003685)= 1/256

    还是给出C语言的实现代码,我们采用循序渐进的方法,先给出浮点数的实现(因为用到了浮点数,所以并没有减少乘法运算量,查找的效率也比二分查找法要低,理论上说这个算法实现很低效。不过这个代码的目的在于给出算法实现的示意性说明,还是有意义的)。

    double my_atan4(double x, double y)
    {
        const double tangent[] = {1.0, 1 / 2.0, 1 / 4.0, 1 / 8.0, 1 / 16.0,
                                  1 / 32.0, 1 / 64.0, 1 / 128.0, 1 / 256.0, 1 / 512.0,
                                  1 / 1024.0, 1 / 2048.0, 1 / 4096.0, 1 / 8192.0, 1 / 16384.0
                                 };
        const double angle[] = {45.0, 26.565051177078, 14.0362434679265, 7.1250163489018, 3.57633437499735,
                                1.78991060824607, 0.8951737102111, 0.4476141708606, 0.2238105003685, 0.1119056770662,
                                0.0559528918938, 0.027976452617, 0.01398822714227, 0.006994113675353, 0.003497056850704
                               };
    
        int i = 0;
        double x_new, y_new;
        double angleSum = 0.0;
    
        for(i = 0; i < 15; i++)
        {
            if(y > 0)
            {
                x_new = x + y * tangent[i];
                y_new = y - x * tangent[i];
                x = x_new;
                y = y_new;
                angleSum += angle[i];
            }
            else
            {
                x_new = x - y * tangent[i];
                y_new = y + x * tangent[i];
                x = x_new;
                y = y_new;
                angleSum -= angle[i];
            }
            printf("Debug: i = %d angleSum = %f, angle = %f, ρ = %f\n", i, angleSum, angle[i], hypot(x, y));
        }
        return angleSum;
    }
    程序运行的输出结果如下:
    Debug: i = 0 angleSum = 45.000000, angle = 45.000000, ρ = 316.227766
    Debug: i = 1 angleSum = 71.565051, angle = 26.565051, ρ = 353.553391
    Debug: i = 2 angleSum = 57.528808, angle = 14.036243, ρ = 364.434493
    Debug: i = 3 angleSum = 64.653824, angle = 7.125016, ρ = 367.270602
    Debug: i = 4 angleSum = 61.077490, angle = 3.576334, ρ = 367.987229
    Debug: i = 5 angleSum = 62.867400, angle = 1.789911, ρ = 368.166866
    Debug: i = 6 angleSum = 63.762574, angle = 0.895174, ρ = 368.211805
    Debug: i = 7 angleSum = 63.314960, angle = 0.447614, ρ = 368.223042
    Debug: i = 8 angleSum = 63.538770, angle = 0.223811, ρ = 368.225852
    Debug: i = 9 angleSum = 63.426865, angle = 0.111906, ρ = 368.226554
    Debug: i = 10 angleSum = 63.482818, angle = 0.055953, ρ = 368.226729
    Debug: i = 11 angleSum = 63.454841, angle = 0.027976, ρ = 368.226773
    Debug: i = 12 angleSum = 63.440853, angle = 0.013988, ρ = 368.226784
    Debug: i = 13 angleSum = 63.433859, angle = 0.006994, ρ = 368.226787
    Debug: i = 14 angleSum = 63.437356, angle = 0.003497, ρ = 368.226788
    
     z = 63.437356

    有了上面的准备,我们可以来讨论定点数算法了。所谓定点数运算,其实就是整数运算。我们用256 表示1度。这样的话我们就可以精确到1/256=0.00390625 度了,这对于大多数的情况都是足够精确的了。256 表示1度,那么45度就是 45*256 = 115200。其他的度数以此类推。

    序号

    度数

    ×256

    取整

    1

    45.0

    11520

    11520

    2

    26.565051177078

    6800.65310133196

    6801

    3

    14.0362434679265

    3593.27832778918

    3593

    4

    7.1250163489018

    1824.00418531886

    1824

    5

    3.57633437499735

    915.541599999322

    916

    6

    1.78991060824607

    458.217115710994

    458

    7

    0.8951737102111

    229.164469814035

    229

    8

    0.4476141708606

    114.589227740302

    115

    9

    0.2238105003685

    57.2954880943458

    57

    10

    0.1119056770662

    28.647853328949

    29

    11

    0.0559528918938

    14.3239403248137

    14

    12

    0.027976452617

    7.16197186995294

    7

    13

    0.01398822714227

    3.58098614841984

    4

    14

    0.006994113675353

    1.79049310089035

    2

    15

    0.003497056850704

    0.8952465537802

    1


    C 代码如下:

    int my_atan5(int x, int y)
    {
        const int angle[] = {11520, 6801, 3593, 1824, 916, 458, 229, 115, 57, 29, 14, 7, 4, 2, 1};
    
        int i = 0;
        int x_new, y_new;
        int angleSum = 0;
    
        x *= 1024;// 将 X Y 放大一些,结果会更准确
        y *= 1024;
    
        for(i = 0; i < 15; i++)
        {
            if(y > 0)
            {
                x_new = x + (y >> i);
                y_new = y - (x >> i);
                x = x_new;
                y = y_new;
                angleSum += angle[i];
            }
            else
            {
                x_new = x - (y >> i);
                y_new = y + (x >> i);
                x = x_new;
                y = y_new;
                angleSum -= angle[i];
            }
            printf("Debug: i = %d angleSum = %d, angle = %d\n", i, angleSum, angle[i]);
        }
        return angleSum;
    }

    计算结果如下:

    Debug: i = 0 angleSum = 11520, angle = 11520
    Debug: i = 1 angleSum = 18321, angle = 6801
    Debug: i = 2 angleSum = 14728, angle = 3593
    Debug: i = 3 angleSum = 16552, angle = 1824
    Debug: i = 4 angleSum = 15636, angle = 916
    Debug: i = 5 angleSum = 16094, angle = 458
    Debug: i = 6 angleSum = 16323, angle = 229
    Debug: i = 7 angleSum = 16208, angle = 115
    Debug: i = 8 angleSum = 16265, angle = 57
    Debug: i = 9 angleSum = 16236, angle = 29
    Debug: i = 10 angleSum = 16250, angle = 14
    Debug: i = 11 angleSum = 16243, angle = 7
    Debug: i = 12 angleSum = 16239, angle = 4
    Debug: i = 13 angleSum = 16237, angle = 2
    Debug: i = 14 angleSum = 16238, angle = 1
    
     z = 16238

    16238/256=63.4296875度,精确的结果是63.4349499度,两个结果的差为0.00526,还是很精确的。

    到这里 CORDIC 算法的最核心的思想就介绍完了。当然,这里介绍的只是CORDIC算法最基本的内容,实际上,利用CORDIC 算法不光可以计算 atan 函数,其他的像 SinCosSinhCosh 等一系列的函数都可以计算,不过那些都不在本文的讨论范围内了。另外,每次旋转时到原点的距离都会发生变化,而这个变化是确定的,因此可以在循环运算结束后以此补偿回来,这样的话我们就同时将ρ,θ)都计算出来了。

    想进一步深入学习的可以阅读 John Stephen Walther 2000年发表在 Journal of VLSI signal processing systems for signal, image and video technology上的综述性文章“The Story of Unified Cordic”。


    展开全文
  • 4个基本算法思想:穷举、递推、递归、概率 ...暴力破解,n层for循环。列举每一种可能。 例题: 鸡兔同笼:一个笼子有35个头,94只脚,问鸡和兔各有多少? 解题:鸡兔同笼 二、递推: 简单的动态规划,根...

    4个基本算法思想:穷举、递推、递归、概率

    内容:这4个基本算法思想是解决基础问题的很实用的方法。这里开始其实就已经是把所有需要的知识准备好了,之后就要开始解题了。此文为初级算法总结的子篇第六章——4个基本算法思想。

    一、穷举

    暴力破解,n层for循环。列举每一种可能。

    例题:

    鸡兔同笼:一个笼子有35个头,94只脚,问鸡和兔各有多少?

    解题:鸡兔同笼

    二、递推:

    简单的动态规划,根据递推公式,累加。

    例题:

    斐波那契函数:F(n) =  F(n-1)+ F(n-2),随便给一个n,问F(n)为多少。

    解题:斐波那契

    3、普通递归:

    化解问题逐渐变小(从n到1)

    例题:求n的阶乘

    public static int njiecheng(int n) {
    
        if (n==1) {
        return 1;
        }
        else {
        return n * njiecheng(n-1);
        }
    }

    4、概率:

    使用random随机数,数量足够大的时候,得到近似结果。

    例题:

    计算圆周率π:π = S / R²,根据随机点算出圆的面积,然后通过公式算出π。

     

    展开全文
  • 五大算法思想

    千次阅读 2015-07-09 13:53:19
    五大算法思想 分治算法 一、基本概念  在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题...
  • 排序算法之快速排序实现及算法思想

    千次阅读 多人点赞 2021-03-24 20:18:00
    算法思想: 第一步:确定分界点 可取q[l]、q[r]、q[(l+r)/2]、随机。 假设确定好一个数x 第二步(最难):重新划分区间,通过x将区间分为两部分,使第一个区间所有都小于等于x,第二个区间所有都大于等于x。 第三...
  • 五种基本算法思想

    万次阅读 多人点赞 2017-12-25 16:31:57
    1.穷举算法思想 穷 举 算 法 (ExhaustiveA ttack method)是 最 简 单 的 一 种 算 法 ,其依赖于计算机的强大计算能力来 穷 尽 每 一 种 可 能 的 情 况 ,从 而 达 到 求 解 问 题 的 目 的 。穷 举 算 法 效 ...
  • 循环冗余校验(CRC)算法入门引导

    万次阅读 多人点赞 2012-08-19 12:42:34
    写给嵌入式程序员的循环冗余校验(CRC)算法入门引导 前言 CRC校验(循环冗余校验)是数据通讯中最常采用的校验方式。在嵌入式软件开发中,经常要用到CRC 算法对各种数据进行校验。因此,掌握基本的CRC算法应是...
  •   Hash,也叫哈希或散列,就是把任意长度的输入(也叫预映射),通过散列算法,变换成固定长度的输出,该输出就是散列值。   若结构中存在和关键字key相等的记录,则必定在H(key)的存储位置上。称该H(key)为哈希...
  • 深度学习前沿算法思想

    千次阅读 2017-02-20 16:43:09
    转自:深度学习前沿算法思想 导读 第一版: 深度学习前沿算法思想 深度学习实践:使用Tensorflow实现快速风格迁移 行为识别:让机器学会“察言观色”第一步 第二版: 谷歌首届 TensorFlow 开发者峰会 重磅...
  • 选择排序算法思想

    万次阅读 多人点赞 2018-07-15 15:50:50
    选择排序的基本思想是:如果有N个元素需要排序,那么首先从N个元素中找到最小的那个元素与第0位置上的元素交换(说明一点,如果没有比原本在第0位置上的元素小的就不用交换了,后面的同样是),然后再从剩下的N-1个...
  • 这篇文章主要介绍了Python递归函数 二分查找算法实现解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一、初始递归 递归函数:在一个函数里在调用这个函数...
  • 可以理解硬件计算三角函数
  • 操作系统-循环首次适应算法

    万次阅读 2017-11-27 20:30:18
    循环首次适应算法介绍 每次为进程分配空间的时候,从上一次刚分配过的空闲区的下一块开始寻找,比如,初始化的内存空闲区是用户输入的max大小,没有进行回收之前之前必定是只有最后一块是空闲的,但是经过回收之后...
  • 几种算法思想

    千次阅读 2011-06-20 13:46:00
    采用递归描述的算法通常有这样的特征: 1)为求解规模为N的问题,设法将它分解成规模较小的问题; 2)然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综
  • 比如说我今天看的Crc循环冗余校验算法和rand随机数产生算法。  CRC算法全称循环冗余校验算法。CRC校验的基本思想是利用线性编码理论,在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的监督码(既...
  • while expression: statement(s) statement(s) for基本语法如下: for iterating_var in sequence: for iterating_var in sequence: statements(s) statements(s) 下面以最简单的冒泡排序算法来补充循环嵌套知识。...
  • 算法思想——穷举 (用java语言实现 鸡兔同笼问题,韩信点兵问题等) 2. 递推 简单的动态规划,根据递推公式,累加。 经典案例: 斐波那契函数:F(n) = F(n-1)+ F(n-2),随便给一个n,问F(n)为多少。java语言...
  • 算法系列之十五:循环和递归在算法中的应用

    万次阅读 多人点赞 2012-05-20 23:11:36
    一、递归和循环的关系 1、 递归的定义 顺序执行、循环和跳转是冯·诺依曼计算机体系中程序设计语言的三大基本控制结构,这三种控制结构构成了千姿百态的算法,程序,乃至整个软件世界。递归也算是一种程序控制结构...
  • 【数据结构】--- kmp算法和strstr函数

    千次阅读 多人点赞 2019-10-25 10:42:03
    kmp算法和strstr函数 注:现实生活中,字符串匹配在很多的应用场景里都有着极其重要的作用,包括生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测等等,至此诞生了很多的算法,那么我们今天就来...
  • 高效的循环左移算法

    千次阅读 2010-09-14 13:06:00
    将R中的序列循环左移p(0)个位置,即将R中的数据由 (X0,X1,……,Xn-1)变换为(Xp, Xp+1, …,Xn-1,X0,X1,…,Xp-1)要求: (1) 给出算法的基本设计思想。 (2) 根据设计思想,采用C或C++或JAVA语言...
  • 穷举算法(Exhaustive Attack method)...琼剧算法的基本思想就是从所有可能的情况中搜索正确的答案,其执行步骤如下: (1)对于一种可能的情况,计算其结果。 (2)判断结果是否符合要求,如果不满足则执行第(1)步
  • 递归:程序调用自身的编程技巧称为递归,是函数自己调用自己。 使用递归要注意的有3点: 递归就是在过程或函数里面调用自身; 在使用递归时,必须有一个明确的递归结束条件,称为递归出口. 递归包含回溯和递推两个阶段...
  • 蚁群算法解决多峰函数优化问题

    千次阅读 2020-03-28 03:23:43
    一、多峰优化问题概述       ...二、蚁群问题解决函数多峰寻优问题思想         以一维函数y=f(x)的极小值寻优为例,对函...
  • C# 遗传算法函数最大值

    千次阅读 2010-06-15 01:03:00
    遗传算法简介,计算函数最大值 C# 示例
  • C语言通用双向循环链表操作函数

    千次阅读 2017-05-17 15:30:42
     相比Linux内核链表宿主结构可有多个链表结构的优点,本函数集侧重封装性和易用性,而灵活性和效率有所降低。  可基于该函数集方便地构造栈或队列集。  本函数集暂未考虑并发保护。   一 概念  链表是一...
  • 基于粒子群算法与最小二乘拟合函数参数

    千次阅读 多人点赞 2020-04-07 21:30:49
    容易陷入局部最优解的情况,因此,在参数拟合部分会用到现代优化算法,现代优化算法常用的有遗传算法,模拟退火,蚁群算法,粒子群算法等等由于之前地统计实验遗传写的拟合变异函数比较容易陷入局部...
  • 不拘一格编程序——循环打印算法

    千次阅读 热门讨论 2011-07-22 12:57:05
    循环打印算法 作者:朱云翔     小说中经常有人说某某将领打仗天马行空,不拘一格,让敌人防不胜防,比如《寻秦记》中的李牧;比如《大唐双龙传》中的寇少。  编程序时也要有怎样的思想,不能被条条框框所束缚,...
  • 简而言之,遗传算法就是通过每次选择比较好的个体进入下一次循环来保证每一轮解的最优特性,其核心思想有以下几个方面。 (1)初始化值(染色体),转化成二进制的形式(为了方便和变异) (2)使用轮盘赌算法设计...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 80,612
精华内容 32,244
关键字:

循环函数for的算法思想