常用算法1 遍试算法2 迭代算法3 递归算法

77 阅读 0 评论 51 点赞

我是靠谱客的博主兴奋雨，最近开发中收集的这篇文章主要介绍常用算法1 遍试算法2 迭代算法3 递归算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1 遍试算法

逻辑上，是对所有可能的情况进行判断
形式上：for中用if

//韩信点兵问题
//韩信点兵又称为中国剩余定理，相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每3人//一列余1人、5人一列余2人、7人一列余4人、13人一列余6人……刘邦茫然而不知其数。问怎么求///出来多少士兵？
using System;
class HanXin
{
static void Main()
{
for( int n=1; n<=105; n++)
{
if( n%3==2 && n%5==3 && n%7==5 )
Console.WriteLine(n);
}
}
}

//水仙花数
//水仙花数是指一个 n 位数（n≥3 ），它的每个位上的数字的n次幂之和等于它本身
//（例如：1^3 + 5^3+ 3^3 = 153）。
using System;
public class All_153
{
public static void Main(string [] args)
{
for( int a=1; a<=9; a++)
for( int b=0; b<=9; b++)
for( int c=0; c<=9; c++)
if( a*a*a+b*b*b+c*c*c == 100*a+10*b+c)
Console.WriteLine( 100*a+10*b+c);
}
}

//完全数
//如果一个数恰好等于它的因子之和，则称该数为完全数
using System;
class All_628
{
public static void Main( string[] args){
for( int n=1; n<=9999; n++)
if( n==divsum(n) ) Console.WriteLine(n);
}
//因子求和
public static int divsum( int n){
int s = 0;
for( int i=1; i<n; i++)
if( n%i == 0) s+=i;
return s;
}
}

//相亲数
//两个正整数中，彼此的全部约数之和（本身除外）与另一方相等
using System;
class All_220
{
public static void Main( string[] args){
for( int n=1; n<=9999; n++){
int s = divsum(n);
if( n<s && divsum(s)==n )
Console.WriteLine(n +"," + s);
}
}
public static int divsum( int n){
int s = 0;
for( int i=1; i<n; i++)
if( n%i == 0 ) s+=i;
return s;
}
}

//哥德巴赫猜想
//任一大于2的偶数都可写成两个质数之和
using System;
class GDBH
{
static void Main()
{
for (int n = 6; n <= 100; n+=2)
{
for (int a = 3; a<=n/2; a+=2)
{
int b = n - a;
if (IsPrime(a) && IsPrime(b))
{
Console.WriteLine(n + "=" + a + "+" + b);
break;
}
}
}
}
//判断是不是质数
static bool IsPrime(int a)
{
for (int i = 2; i <= a / 2; i++)
{
if (a % i == 0) return false;
}
return true;
}
}

2 迭代算法

逻辑上，多次使用同一算法
形式上，while中用a=f(a)

//求平方根
using System;
public class Sqrt
{
public static void Main(string[] args)
{
Console.WriteLine(sqrt(98));
Console.WriteLine(Math.Sqrt(98.0));
}
//x*x = a，和牛顿法求零点相似
static double sqrt(double a)
{
double x = 1.0;
do
{
Console.WriteLine(x + "," + a / x);
x = (x + a / x) / 2;
} while (Math.Abs(x * x - a) / a > 1e-11);
return x;
}
}

//倍边法求PI
using System;
class TestDebugPi
{
static void Main(){
double a=1;
for(int n=1; n<=10; n++ )
{
a = Math.Sqrt(2 - Math.Sqrt(4 - a * a));
double pi = a * 3 * Math.Pow(2,n);
Console.WriteLine( pi );
}
Console.WriteLine( Math.PI );
//请调试:如果n<=100,如何?
}
}

3 递归算法

逻辑上，一个问题转化为同样的问题
形式上，自己调用自己，f(n)中用f(n-1)
基本思想：分而治之
需要存在一个出口

//求阶乘
using System;
public class Fac
{
public static void Main(string [] args)
{
Console.WriteLine("Fac of 5 is" + Fac(5));
}
static public long Fac(int n)
{
if(n == 0 || n == 1)//出口
return 1;
else
return n * Fac(n-1);
}
}

//菲波那切数列
//走台阶问题，楼梯有n个台阶，上楼可以一步上1阶，也可以一步上2阶，一共有多少种上楼的方法？
using System;
public class Fibonacci
{
public static void Main(string [] args)
{
Console.WriteLine("Fibonacci(10) is " + fib(10) );
}
static long fib(int n)
{
if( n==1 ) return 1;
else if(n==2) return 2;
else return (fib(n-1) + fib(n-2));
}
}

//画树
using System;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;
using System.Data;
public class Form1 : Form
{
public Form1()
{
this.AutoScaleBaseSize = new Size(6, 14);
this.ClientSize = new Size(400, 400);
this.Paint += new PaintEventHandler(this.Form1_Paint);
this.Click += new EventHandler(this.Redraw);
}
static void Main()
{
Application.Run(new Form1());
}
private void Form1_Paint(object sender, PaintEventArgs e)
{
graphics = e.Graphics;
drawTree(15, 200, 380, 100, -PI / 2);
}
private void Redraw(object sender, EventArgs e)
{
this.Invalidate();//就会引起.paint事件
}
private Graphics graphics;
const double PI = Math.PI;
double th1 = 35 * Math.PI / 180;//角度
double th2 = 25 * Math.PI / 180;//角度
double per1 = 0.6;//比例系数
double per2 = 0.7;//比例系数
Random rnd = new Random();
double rand()
{
return rnd.NextDouble();
}
//画树
//递归n次，长度length，角度th
void drawTree(int n,
double x0, double y0, double leng, double th)
{
if (n == 0) return;
double x1 = x0 + leng * Math.Cos(th);
double y1 = y0 + leng * Math.Sin(th);
drawLine(x0, y0, x1, y1);
//第一条分支
drawTree(n - 1, x1, y1, per1 * leng * (0.5 + rand()), th + th1 * (0.5 + rand()));
//第二条分支
drawTree(n - 1, x1, y1, per2 * leng * (0.4 + rand()), th - th2 * (0.5 + rand()));
//第三条分支
if (rand() > 0.6)
drawTree(n - 1, x1, y1, per2 * leng * (0.4 + rand()), th - th2 * (0.5 + rand()));
}
//画线
void drawLine(double x0, double y0, double x1, double y1)
{
graphics.DrawLine(
Pens.Blue,
(int)x0, (int)y0, (int)x1, (int)y1);
}
}