算法(一)
2017-10-17 本文已影响9人
小熊翻译App
以下算法参考 <<算法>> 第4版[美] Robert Sedgewick
1. 欧几里德算法
- (void)viewDidLoad {
[super viewDidLoad];
[self calculateGreatestCommonDivisorP:30 q:6]; //欧几里德算法:求两个数的最大公约数
}
#pragma mark - 欧几里德算法
/**
计算两个非负整数 p 和 q 的最大公约数:若 q 是 0，则最大公约数为 p。否则，将 p 除以 q得到余数r，p和q的最大公约数即为q和 r 的最大公约数。
greatest common divisor: 最大公因子
*/
- (int)calculateGreatestCommonDivisorP:(int)p q:(int)q {
NSLog(@"p 和 q 的最大公约数============ %d", gcd(p, q));
return gcd(p,q);
}
int gcd (int p, int q) {
if (q == 0) {
return p;
}
int r = p % q;
return gcd(q, r);
}
2. 找出数组中组大的元素
- (void)viewDidLoad {
[super viewDidLoad];
NSArray *array = @[@2.6, @3, @9.6, @8, @5, @6];
[self getMaxNumInArray:array]; //找出数组中组大的元素
}
- (NSNumber *)getMaxNumInArray:(NSArray *)array
{
double max = [array[0] doubleValue];
for (int i = 1; i < array.count; i ++) {
if ([array[i] doubleValue] > max) {
max = [array[i] doubleValue];
}
}
NSLog(@"MaxNumInArray===========%@", @(max));
return @(max);
}
注:这里不能直接用 NSNumber, 直接用 NSNumber 浮点数会出错.
3. 计算数组元素的平均值
- (void)viewDidLoad {
[super viewDidLoad];
NSArray *array = @[@2.6, @3, @9.6, @8, @5, @6];
[self calculateAverageInArray:array]; // 计算数组元素的平均值
}
- (NSNumber *)calculateAverageInArray:(NSArray *)array {
NSInteger length = array.count;
double sum = 0.0;
double average = 0.0;
for (NSInteger i = 0; i < length; i ++) {
sum += [array[i] doubleValue];
average = sum / length;
}
NSLog(@"calculateAverage===========%@", @(average));
return @(average);
}
4. 复制数组
注:示例数组中是NSNumber类型元素,其它类型需要另写方法
- (void)viewDidLoad {
[super viewDidLoad];
[self copyArray:array]; // 复制数组:示例数组中是数字
}
- (NSArray *)copyArray:(NSArray *)array {
NSInteger length = array.count;
NSMutableArray * copyArrayM = [NSMutableArray array];
for (NSInteger i = 0; i < length; i ++) {
copyArrayM[i] = array[i];
}
NSArray *copyArray = copyArrayM;
return copyArray;
}
5. 颠倒数组元素的顺序
- (void)viewDidLoad {
[super viewDidLoad];
[self reverseArray:array]; // 颠倒数组元素的顺序
}
- (NSArray *)reverseArray:(NSArray *)array {
NSInteger N = array.count;
NSMutableArray *arrayM = [NSMutableArray array];
for (NSInteger i = 0; i < N; i ++) {
[arrayM addObject:array[i]];
}
for (NSInteger i = 0; i < N/2; i++) {
NSNumber *temp = arrayM[i];
arrayM[i] = arrayM[N-1-i];
arrayM[N-i-1] = temp;
}
array = arrayM;
return array;
}
-----------典型静态方法的实现-------------
6. 计算一个数的绝对值:浮点数和整数
- (void)viewDidLoad {
[super viewDidLoad];
NSNumber *numAbs = [self calculateNumAbs:-234];
NSLog(@"calculateDoubleAbs========%@", numAbs);
}
- (NSNumber *)calculateNumAbs:(double)x {
if (x<0.0) {
return @(-x);
}
else {
return @(x);
}
}
7. 判定一个数是否是素数:prime number
- (void)viewDidLoad {
[super viewDidLoad];
BOOL isPrime = [self isPrime:17]; // 判定一个数是否是素数
NSLog(@"isPrime===========%d", isPrime);
}
- (BOOL)isPrime:(NSInteger)N {
if (N < 2) {
return false;
}
for (NSInteger i = 2; i*i <= N; i++) {
if (N % i == 0) {
return false;
}
}
return true;
}
8. 计算平方根(牛顿迭代法)
- (void)viewDidLoad {
[super viewDidLoad];
double numSqrt = [self calculateSqrt:-1];
NSLog(@"numSqrt=========%f", numSqrt);
}
- (double)calculateSqrt:(double)c {
if (c < 0) {
return NAN;
}
double err = 1e-15;
double t = c;
while (fabs(t - c/t) > err * t) {
t = (c/t + t) / 2.0;
}
return t;
}
9. 计算直角三角形的斜边
- (void)viewDidLoad {
[super viewDidLoad];
double hypotenuse = [self calculateHypotenuse:5 :12];
NSLog(@"hypotenuse=========%f", hypotenuse);
}
- (double)calculateHypotenuse:(double)a :(double)b {
return sqrt(a*a + b*b);
}
10. 计算调和级数
- (void)viewDidLoad {
[super viewDidLoad];
double HarmonicSeries = [self calculateHarmonicSeries:5];
NSLog(@"HarmonicSeries=========%f", HarmonicSeries);
}
- (double)calculateHarmonicSeries:(NSInteger)N {
double sum = 0.0;
for (int i = 1; i <= N; i++) {
sum += 1.0 / i;
}
return sum;
}
11. 二分查找的递归实现
注: 二分查找的递归实现: 数组内数字大小是有序的(从大到小)
- (void)viewDidLoad {
[super viewDidLoad];
NSArray *intArray = @[@2, @3, @4, @10, @19, @20];
NSInteger rankNum = [self rank:20 :intArray];
NSLog(@"rankNum=========%ld", (long)rankNum);
}
- (NSInteger)rank:(NSInteger)key :(NSArray<NSNumber *> *)array {
return [self rank:key :array :0 :array.count - 1];
}
- (NSInteger)rank:(NSInteger)key :(NSArray *)array :(NSInteger)low :(NSInteger)high {
//如果key存在于a[]中，它的索引不会小于low且不会大于high
if (low > high) {
return -1;
}
NSInteger mid = low + (high - low) / 2;
if (key < [array[mid] integerValue]) { //若小于array[mid],则往前查找
return [self rank:key :array :low :mid-1];
}
else if (key > [array[mid] integerValue]) { //若大于array[mid],则往后查找
return [self rank:key :array :mid+1 :high];
}
else {
return mid;
}
}
关于递归:编写递归代码时最重要的有以下三点
1. 递归总有一个最简单的情况——方法的第一条语句总是一个包含 return 的条件语句。
2. 递归调用总是去尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况。上面的代码中，第四个参数和第三个参数的差值一直在缩小。
3. 递归调用的父问题和尝试解决的子问题之间不应该有交集。上面的代码中，两个子问题各自操作的数组部分是不同的。
-----------随机数---------
12. 随机返回 [a,b) 之间的一个 double 值
- (void)viewDidLoad {
[super viewDidLoad];
double doubleRandom = [self uniform:1 :3];
NSLog(@"doubleRandom=========%f", doubleRandom);
}
- (double)uniform:(double)a :(double)b {
#define ARC4RANDOM_MAX 1000000
return a + ((double)(arc4random()%ARC4RANDOM_MAX)/ARC4RANDOM_MAX) * (b-a);
}
13. 随机返回 [0,N-1] 之间的整数,值域:[0,N-1]
- (void)viewDidLoad {
[super viewDidLoad];
NSInteger intRandomZeroToHigh = [self arc4randomHigh:5];
NSLog(@"intRandomZeroToHigh=========%ld", (long)intRandomZeroToHigh);
}
- (NSInteger)arc4randomHigh:(NSInteger)high {
return arc4random() % high;
}
14. 随机返回 [low,high-1] 之间的整数,值域:[low,high]
- (void)viewDidLoad {
[super viewDidLoad];
NSInteger intRandomLowToHigh = [self arc4randomLow:3 high:5];
NSLog(@"intRandomLowToHigh=========%ld", (long)intRandomLowToHigh);
}
- (NSInteger)arc4randomLow:(NSInteger)low high:(NSInteger)high {
return low + arc4random() % (high-low);
}
15. 根据离散概率随机返回的 int 值(出现 i 的概率为 a[i])
- (void)viewDidLoad {
[super viewDidLoad];
NSArray *discreteArray = @[@0.2,@0.09,@0.3,@0.11,@0.3]; // a[]中各元素之和必须等于1
NSInteger discrete = [self discrete:discreteArray];
NSLog(@"discrete=======%zd", discrete);
}
- (NSInteger)discrete:(NSArray *)array {
// a[]中各元素之和必须等于1
#define ARC4RANDOM_MAX 1000000
double r = (double)(arc4random()%ARC4RANDOM_MAX)/ARC4RANDOM_MAX; // [0,1)随机数
double sum = 0.0;
for (NSInteger i = 0; i < array.count; i++) {
sum = sum + [array[i] doubleValue];
if (sum >= r) {
return i;
}
}
return -1;
}
16. 随机将 double 数组中的元素排序
- (void)viewDidLoad {
[super viewDidLoad];
NSArray *beforeShuffleArray = @[@2,@10.09,@2.3,@0.11,@6.3];
NSArray *afterShuffleArray = [self shuffle:beforeShuffleArray];
NSLog(@"afterShuffleArray = %@", afterShuffleArray);
}
/// 随机将 double 数组中的元素排序
- (NSMutableArray *)shuffle:(NSArray *)array {
NSMutableArray *arrayM = [NSMutableArray array];
for (NSNumber *num in array) {
[arrayM addObject:num];
}
NSInteger N = arrayM.count;
for (NSInteger i = 0; i < N; i++) {
// 将a[i]和a[i..N-1]中任意一个元素交换
NSInteger r = i + arc4random() % (N-i);
double temp = [arrayM[i] doubleValue];
arrayM[i] = arrayM[r];
arrayM[r] = @(temp);
}
return arrayM;
}
