以下算法參考 <<算法>> 第4版[美] Robert Sedgewick
1. 歐幾里德算法
- (void)viewDidLoad {
[super viewDidLoad];
[self calculateGreatestCommonDivisorP:30 q:6]; //歐幾里德算法:求兩個(gè)數(shù)的最大公約數(shù)
}
#pragma mark - 歐幾里德算法
/**
計(jì)算兩個(gè)非負(fù)整數(shù) p 和 q 的最大公約數(shù):若 q 是 0，則最大公約數(shù)為 p嘿期。否則赡若，將 p 除以 q得到余數(shù)r仓蛆，p和q的最大公約數(shù)即為q和 r 的最大公約數(shù)睬涧。
greatest common divisor: 最大公因子
*/
- (int)calculateGreatestCommonDivisorP:(int)p q:(int)q {
NSLog(@"p 和 q 的最大公約數(shù)============ %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. 找出數(shù)組中最大的元素
- (void)viewDidLoad {
[super viewDidLoad];
NSArray *array = @[@2.6, @3, @9.6, @8, @5, @6];
[self getMaxNumInArray:array]; //找出數(shù)組中組大的元素
}
- (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 浮點(diǎn)數(shù)會(huì)出錯(cuò).
3. 計(jì)算數(shù)組元素的平均值
- (void)viewDidLoad {
[super viewDidLoad];
NSArray *array = @[@2.6, @3, @9.6, @8, @5, @6];
[self calculateAverageInArray:array]; // 計(jì)算數(shù)組元素的平均值
}
- (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. 復(fù)制數(shù)組
注:示例數(shù)組中是NSNumber類型元素,其它類型需要另寫(xiě)方法
- (void)viewDidLoad {
[super viewDidLoad];
[self copyArray:array]; // 復(fù)制數(shù)組:示例數(shù)組中是數(shù)字
}
- (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. 顛倒數(shù)組元素的順序
- (void)viewDidLoad {
[super viewDidLoad];
[self reverseArray:array]; // 顛倒數(shù)組元素的順序
}
- (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;
}
-----------典型靜態(tài)方法的實(shí)現(xiàn)-------------
6. 計(jì)算一個(gè)數(shù)的絕對(duì)值:浮點(diǎn)數(shù)和整數(shù)
- (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. 判定一個(gè)數(shù)是否是素?cái)?shù):prime number
- (void)viewDidLoad {
[super viewDidLoad];
BOOL isPrime = [self isPrime:17]; // 判定一個(gè)數(shù)是否是素?cái)?shù)
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. 計(jì)算平方根(牛頓迭代法)
- (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. 計(jì)算直角三角形的斜邊
- (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. 計(jì)算調(diào)和級(jí)數(shù)
- (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. 二分查找的遞歸實(shí)現(xiàn)
注: 二分查找的遞歸實(shí)現(xiàn): 數(shù)組內(nèi)數(shù)字大小是有序的(從大到小)
- (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[]中舱权，它的索引不會(huì)小于low且不會(huì)大于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;
}
}
關(guān)于遞歸:編寫(xiě)遞歸代碼時(shí)最重要的有以下三點(diǎn)
1. 遞歸總有一個(gè)最簡(jiǎn)單的情況——方法的第一條語(yǔ)句總是一個(gè)包含 return 的條件語(yǔ)句矗晃。
2. 遞歸調(diào)用總是去嘗試解決一個(gè)規(guī)模更小的子問(wèn)題，這樣遞歸才能收斂到最簡(jiǎn)單的情況宴倍。上面的代碼中张症，第四個(gè)參數(shù)和第三個(gè)參數(shù)的差值一直在縮小仓技。
3. 遞歸調(diào)用的父問(wèn)題和嘗試解決的子問(wèn)題之間不應(yīng)該有交集。上面的代碼中俗他，兩個(gè)子問(wèn)題各自操作的數(shù)組部分是不同的脖捻。
-----------隨機(jī)數(shù)---------
12. 隨機(jī)返回 [a,b) 之間的一個(gè) 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. 隨機(jī)返回 [0,N-1] 之間的整數(shù),值域:[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. 隨機(jī)返回 [low,high-1] 之間的整數(shù),值域:[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. 根據(jù)離散概率隨機(jī)返回的 int 值(出現(xiàn) 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)隨機(jī)數(shù)
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. 隨機(jī)將 double 數(shù)組中的元素排序
- (void)viewDidLoad {
[super viewDidLoad];
NSArray *beforeShuffleArray = @[@2,@10.09,@2.3,@0.11,@6.3];
NSArray *afterShuffleArray = [self shuffle:beforeShuffleArray];
NSLog(@"afterShuffleArray = %@", afterShuffleArray);
}
/// 隨機(jī)將 double 數(shù)組中的元素排序
- (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]中任意一個(gè)元素交換
NSInteger r = i + arc4random() % (N-i);
double temp = [arrayM[i] doubleValue];
arrayM[i] = arrayM[r];
arrayM[r] = @(temp);
}
return arrayM;
}
