以下是几个简单的算法解析,你也可以只看题目,进行挑战,希望有更高效的算法
啊哈挑战官网
- 题目:153是一个非常优美的数
153=1*1*1+5*5*5+3*3*3
你知道在三位整数（abc）中，满足abc=a*a*a+b*b*b+c*c*c这个条件的最大的整数是什么?
解答:
- (void)viewDidLoad {
[super viewDidLoad];
NSInteger max = [self calculateMax];
NSLog(@"max==========%zd", max);
}
- (NSInteger)calculateMax {
NSMutableArray *arrayM = [NSMutableArray array];
for (NSInteger i = 100; i <= 999; i++) {
// 分别获取字符串的第一个,第二个,第三个字符
NSString *numString = [NSString stringWithFormat:@"%zd", i];
NSInteger x = [[numString substringWithRange:NSMakeRange(0,1)] intValue];
NSInteger y = [[numString substringWithRange:NSMakeRange(1,1)] intValue];
NSInteger z = [[numString substringWithRange:NSMakeRange(2,1)] intValue];
NSString *xyzString = [NSString stringWithFormat:@"%ld%ld%ld", (long)x, (long)y, (long)z];
NSInteger xyz = [xyzString integerValue];
NSInteger xyzMul = x*x*x + y*y*y + z*z*z;
if (xyz == xyzMul) {
[arrayM addObject:@(xyz)];
}
}
NSNumber *resultNum = arrayM.lastObject;
NSLog(@"resultNum==========%@", resultNum);
NSInteger max = [resultNum integerValue];
return max;
}
答案: 407
- 题目: 请问1~123456之间所有7的倍数和末尾含7的数的和是？
- (void)viewDidLoad {
[super viewDidLoad];
long long sum = [self calculateSumLow:1 high:123456 divisor:7];
NSLog(@"0~123456sum=============%lld", sum);
}
- (long long)calculateSumLow:(long long)low high:(long long)high divisor:(long long)divisor {
NSMutableArray *arrayM = [NSMutableArray array];
for (long long i = 1; i <= high; i ++) {
NSString *numString = [NSString stringWithFormat:@"%lld", i];
long long lastNum = [[numString substringFromIndex:numString.length-1] longLongValue];
if (i%divisor==0 || lastNum == divisor) {
[arrayM addObject:@(i)];
}
}
long long sum = 0;
for (NSNumber *num in arrayM) {
long long k = [num longLongValue];
sum = sum+k;
}
return sum;
}
答案: 28217
- 题目:斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21……从第三项开始每一项是前两项的和。
请问斐波那契数列第45项是多少呢？
更多斐波那契数列的知识，请访问百度百科。
- (void)viewDidLoad {
[super viewDidLoad];
long long FibonacciItemNum = [self calculateFibonacciSequenceItem:45];
NSLog(@"itemNum========%lld", FibonacciItemNum);
}
- (long long)calculateFibonacciSequenceItem:(long long)item {
NSMutableArray *arrayM = [NSMutableArray array];
for (long long i=0; i<=1; i++) {
[arrayM addObject:@(1)];
}
for (long long i = 2; i <= item-1; i++) {
long long num = 0;
if (i >= 2) {
num = [arrayM[i-1] longLongValue] + [arrayM[i-2] longLongValue];
[arrayM addObject:@(num)];
}
}
NSLog(@"-----------%lld,%@,%@", [arrayM.lastObject longLongValue], arrayM[arrayM.count-2], arrayM[arrayM.count-3]);
NSLog(@"FibonacciArrayM==========%@", arrayM);
return [arrayM.lastObject longLongValue];
}
答案: 1134903170
- 题目:2~12345中有多少个质数？
- (void)viewDidLoad {
[super viewDidLoad];
long long primeNumberCount = [self calculatePrimeNumberCount:2 high:12345];
NSLog(@"primeNumberCount============%lld", primeNumberCount);
}
- (long long)calculatePrimeNumberCount:(long long)low high:(long long)high {
NSMutableArray *arrayM = [NSMutableArray array];
for (long long i = 2; i < high; i++) {
BOOL isPrime = [self isPrime:i];
if (isPrime==YES) {
[arrayM addObject:@(i)];
}
}
return arrayM.count;
}
/// 判定一个数是否是素数:prime number
- (BOOL)isPrime:(long long)N {
if (N < 2) {
return NO;
}
for (NSInteger i = 2; i*i <= N; i++) {
if (N % i == 0) {
return NO;
}
}
return YES;
}
答案: 1474
- 题目: 质数和, 2 ~ 10以内的质数有2,3,5,7。所以2 ~ 10之间所有质数的和是17。
那么2 ~ 100之间所有质数的和是？
- (void)viewDidLoad {
[super viewDidLoad];
long long primeNumberSum = [self calculatePrimeNumberSumLow:2 high:100];
NSLog(@"primeNumberSum========%lld", primeNumberSum);
}
- (long long)calculatePrimeNumberSumLow:(long long)low high:(long long)high{
NSArray *primeArray = [self calculatePrimeNumber:low high:high];
long long sum = 0;
for (NSNumber *num in primeArray) {
sum = sum + [num longLongValue];
}
return sum;
}
- (NSArray *)calculatePrimeNumber:(long long)low high:(long long)high {
NSMutableArray *arrayM = [NSMutableArray array];
for (long long i = low; i < high; i++) {
BOOL isPrime = [self isPrime:i];
if (isPrime==YES) {
[arrayM addObject:@(i)];
}
}
NSArray *array = arrayM.copy;
return array;
}
/// 判定一个数是否是素数:prime number
- (BOOL)isPrime:(long long)N {
if (N < 2) {
return NO;
}
for (NSInteger i = 2; i*i <= N; i++) {
if (N % i == 0) {
return NO;
}
}
return YES;
}
答案: 1060
- 题目: 最大质因子,将20分解质因数20=2＊2＊5，5是最大的质因子。那么将987654321分解质因数，所得到的最大的质因子是？
/*
解析:
Pollard Rho因数分解
1975年，John M. Pollard提出了 Pollard Rho 快速因数分解的方法。该算法时间复杂度为O（n^(1/4)）。
分解质因数代码：
将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。
程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：
(1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。
(2)如果n<>k，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数你n,
重复执行第一步。
(3)如果n不能被k整除，则用k+1作为k的值,重复执行第一步。
*/
- (void)viewDidLoad {
[super viewDidLoad];
long long maxPrimeFactor = [self calculateMaxPrimeFactorWithNum:987654321];
NSLog(@"maxPrimeFactor==========%lld", maxPrimeFactor);
}
- (long long)calculateMaxPrimeFactorWithNum:(long long)num {
for(long long i=2;i<=num;i++)
while(num!=i) {
if(num%i==0) {
printf("%lld",i);
num=num/i;
}
else {
break;
}
}
return num;
}
答案: 379721
- 题目: 相差为2的两个质数称为孪生质数。例如3和5是一对孪生质数，41和43也是一对孪生质数。那么100～200之间共有多少对孪生质数呢？
- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *twinPrimeArrayM = [self calculateTwinPrimeLow:100 high:200];
long long twinPrimeCount = twinPrimeArrayM.count;
NSLog(@"twinPrimeCount====== %lld", twinPrimeCount);
NSLog(@"twinPrimeArrayM====== %@", twinPrimeArrayM);
}
- (NSMutableArray *)calculateTwinPrimeLow:(long long)low high:(long long)high {
NSArray *primeArray = [self calculatePrimeNumber:low high:high];
long long preNum = 0;
long long nextNum = 0;
CGPoint point = CGPointMake(preNum, nextNum);
NSMutableArray *twinPrimeArrayM = [NSMutableArray array];
for (long long i = 1; i < primeArray.count; i++) {
long long diffNum = [primeArray[i] longLongValue] - [primeArray[i-1] longLongValue];
if (diffNum == 2) {
point = CGPointMake([primeArray[i-1] longLongValue], [primeArray[i] longLongValue]);
NSValue *pointValue = [NSValue valueWithCGPoint:point];
[twinPrimeArrayM addObject:pointValue];
}
}
return twinPrimeArrayM;
}
- (NSArray *)calculatePrimeNumber:(long long)low high:(long long)high {
NSMutableArray *arrayM = [NSMutableArray array];
for (long long i = low; i < high; i++) {
BOOL isPrime = [self isPrime:i];
if (isPrime==YES) {
[arrayM addObject:@(i)];
}
}
NSArray *array = arrayM.copy;
return array;
}
/// 判定一个数是否是素数:prime number
- (BOOL)isPrime:(long long)N {
if (N < 2) {
return NO;
}
for (NSInteger i = 2; i*i <= N; i++) {
if (N % i == 0) {
return NO;
}
}
return YES;
}
答案: 7
- 题目: 某一天早晨,有一个猴子摘下了若干个桃子,当即就吃了一半,还不过瘾，又多吃了一个.第二天又将剩下的桃子吃了一半多一个,以后每天早上都吃了前一天剩下的一半多一个.到第10天的时候再想吃的时,发现只剩下一个桃子了.这个贪吃的猴子第一天究竟摘了多少个桃子呢?
- (long long)calculateMomkeyPickPeachWithDays:(long long)days {
long long count = 1; // 初始化第十天桃子的个数
for (long long i = 1; i < days; i++) {
count = (count + 1)*2; // 从倒数第二天开始计算
}
return count;
}
答案: 1534
- 题目:请在5483298756中插入3个乘号，使得乘积最大？请问乘积最大是多少？
- (void)viewDidLoad {
[super viewDidLoad];
long long maxMultiplier = [self calculateMaxMultiplier:5483298756];
NSLog(@"maxMultiplier========== %lld", maxMultiplier);
}
- (long long)calculateMaxMultiplier:(long long)num {
NSString *numString = [NSString stringWithFormat:@"%lld", num];
NSMutableArray *arrayM = [NSMutableArray array];
for (NSInteger i = 1; i < numString.length; i++) {
NSString *firstString = [numString substringWithRange:NSMakeRange(0,i)]; // 截取第一个数:从第一个字符开始,截取i个
long long firstNum = [firstString longLongValue];
NSString *remain1 = [numString substringWithRange:NSMakeRange(i,numString.length-i)];
for (NSInteger j = 1; j < remain1.length; j++) {
NSString *secondString = [remain1 substringWithRange:NSMakeRange(0, j)];
long long secondNum = [secondString longLongValue];
NSString *remain2 = [remain1 substringWithRange:NSMakeRange(j, remain1.length-j)];
for (NSInteger k = 1; k < remain2.length; k++) {
NSString *thirdString = [remain2 substringWithRange:NSMakeRange(0, k)];
long long thirdNum = [thirdString longLongValue];
NSString *forthString = [remain2 substringWithRange:NSMakeRange(k, remain2.length-k)];
long long forthNum = [forthString longLongValue];
long long multiplierNum = firstNum * secondNum *thirdNum * forthNum;
[arrayM addObject:@(multiplierNum)];
}
}
}
// 进行排序
NSArray *array = arrayM;
NSArray *comparableArray = [self insertionComparable:array];
NSLog(@"comparableArray========= %@", comparableArray);
long long maxMultiplier = [comparableArray.lastObject longLongValue];
return maxMultiplier;
}
/// 2. 插入排序
- (NSArray *)insertionComparable:(NSArray *)array {
NSMutableArray *arrayM = [NSMutableArray array];
for (NSNumber *num in array) {
[arrayM addObject:num];
}
NSInteger N = arrayM.count;
// 将array按升序排列
for (NSInteger i = 1; i<N; i++) {
// 将 a[i] 插入到 a[i-1]、a[i-2]、a[i-3]...之中
for (NSInteger j = i; j>0 && arrayM[j] < arrayM[j-1]; j--) {
[arrayM exchangeObjectAtIndex:j withObjectAtIndex:j-1];
}
}
NSArray *comparableArray = arrayM.copy;
return comparableArray;
}
答案: 3540506112
