标签归档:数组

10000以内质数算法(C语言)

质数计算 第一版

判断一个n自然数能否被2, 3, … n-1 整除. 如果它不能被任意一个数整除, 该自然数就是质数.

例如判断13是否是质数

则需要判断13能否被下面任意一个数整除即可
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
因为13无法被其中任意一个数整除, 所有13是一个质数.

接下来判断12是否是质数

判断2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
以为12已经可以被2整除, 所有后面的数不需要继续计算.

10000以内的质数, C语言v1

#include <stdio.h>

int main(void)
{
	int i, no;
	unsigned long counter = 0;    /* 计算乘除的次数 */

	for (no = 2; no <= 10000; no++) {
		for (i = 2; i < no; i++) {
			counter++;
			if (no % i == 0)
				break;
		}
		if (no == i)    // 质数判断方法
			printf("%d\n", no);
	}

	printf("the number of nultiplication and division: %lu\n", counter); // 5775223

	return 0;
}

质数计算 第二版

在程序1中大于2的倍数都不是质数, 比如 4, 6, 8, …

10000以内的质数, C语言v2

#include <stdio.h>

int main(void)
{
	int i, no;
	unsigned long counter = 0;    /* 计算乘除的次数 */

	no = 2;
	printf("%d\n", no++);

	for (; no <= 10000; no += 2) {
		for (i = 2; i < no; i++) {
			counter++;
			if (no % i == 0)
				break;
		}
		if (no == i)    // 质数判断方法
			printf("%d\n", no);
	}

	printf("the number of multiplication and division: %lu\n", counter);    // 5770224

	return 0;
}

与第一版相比, 乘除次数几乎一致, 因为每一次循环都跳过了除以2这个数字

继续阅读

兔子问题

兔子问题来源:

根据高德纳(Donald Ervin Knuth)的《计算机程序设计艺术》(The Art of Computer Programming),1150年印度数学家Gopala和金月在研究箱子包装物件长阔刚好为1和2的可行方法数目时,首先描述这个数列。 在西方,最先研究这个数列的人是比萨的列奥那多(意大利人斐波那契 Leonardo Fibonacci),他描述兔子生长的数目时用上了这数列。

  • 第一个月初有一对刚诞生的兔子
  • 第二个月之后(第三个月初)它们可以生育
  • 每月每对可生育的兔子会诞生下一对新兔子
  • 兔子永不死去

假设在n月有可生育的兔子总共a对,n+1月就总共有b对。在n+2月必定总共有a+b对: 因为在n+2月的时候,前一月(n+1月)的b对兔子可以存留至第n+2月(在当月属于新诞生的兔子尚不能生育)。而新生育出的兔子对数等于所有在n月就已存在的a对

求第N个月兔子对数问题

就是一个斐波那契数列中的一个数
费波那契数列由0和1开始,之后的费波那契系数就由之前的两数相加。首几个费波那契系数是:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

使用递归方法实现(C++)

 

/*************************************************

 *	Name:  			求第N个月兔子对数
 *      Date:   		2014-11-4 23:34:45
 *      Author: 		lnesuper
 *      Version:    	V0.1
 *      Discription:    使用递归解决兔子问题
 *      In math:        F(0) = 0
 *                      F(1) = 1
 *                      F(n) = F(n-1) + F(n-2); (n>2)

**************************************************/

#include <iostream>
using namespace std;

int f(int n);

int main(void) {
	int n;
    cout << "请输入所求第n个月的数值: ";
    cin >> n;
    
	cout << "第" << n << "个月的兔子对数: " <<  f(n) << endl;
	
	return 0;
}

/*
	第一个月:  一对兔子
	第二个月:  二对兔子
  	第 N 个月: 第 N-1 个月的兔子数 + 第 N-2 个月兔子对数
*/
int f(int n) {
	if (1 == n)
		return 1;
	else if (2 == n)
		return 2;
	else
		return f(n - 1) + f(n - 2);
}

/*
Result:

请输入所求第n个月的数值: 40
第40个月的兔子对数: 165580141

--------------------------------
Process exited after 5.223 seconds with return value 0
请按任意键继续. . .

*/

继续阅读