对数器找规律的解题技巧
根据数据量猜解法的技巧
1）C/C++，1秒处理的指令条数为10的8次方
2）Java等语言，1~4秒处理的指令条数为10的8次方
3）这里就有大量的分析提示了
题目1：
小虎去买苹果，商店只提供两种类型的塑料袋，每种类型都有任意数量
1）能装下6个苹果的袋子
2）能装下8个苹果的袋子
小虎可以自由使用两种袋子来装苹果，但是小虎有强迫症，他要求自己使用的袋子数量必须最少，且使用的每个袋子必须装满，给定一个正整数N，返回至少使用多少袋子。如果N无法让使用的每个袋子必须装满，返回-1。
解题提示:利用暴力 打印结果找规律。
#include <iostream>
int minBags(int apple) {
if(apple & 1 == 1)
return -1;
int bag8 = apple / 8;
int bag6 = 0;
int rest = apple - (bag8 * 8);
while (bag8 >= 0)
{
if(rest > 24)
return -1;
if (rest % 6 == 0)
{
return bag8 + (rest / 6);
}
else
{
rest += 8;
bag8--;
}
}
return -1;
}
int main () {
for (int apple = 1; apple < 200; apple++) {
std::cout << apple <<":"<< minBags(apple) <<std:: endl;
}
}
题目2：给定一个正整数N，表示有N份青草统一堆放在仓库里，有一只牛和一只羊，牛先吃，羊后吃，它俩轮流吃草
不管是牛还是羊，每一轮能吃的草量必须是：1，4，16，64…(4的某次方)
谁最先把草吃完，谁获胜，假设牛和羊都绝顶聪明，都想赢，都会做出理性的决定。根据唯一的参数N，返回谁会赢。
解题提示：whoWin是用暴力递归方法解，winner2是暴力递归后找到的规律的解。
#include <iostream>
#include <string>
using namespace std;
string whoWin(int N) {
int base = 1;
while(base <= N) {
if(whoWin(N-base) == "后手") {
return "先手";
}
if(base > N/4) {
break;
}
base *= 4;
}
return "后手";
}
string winner2(int n) {
if (n % 5 == 0 || n % 5 == 2) {
return "后手";
} else {
return "先手";
}
}
int main () {
for (int i = 0; i < 100;i++) {
if(whoWin(i) != winner2(i)) {
cout << "oops" << endl;
break;
}
}
}
题目3： 定义一种数：可以表示成若干（数量>1）连续正数和的数，比如，5=2+3，5就是这样的数；12=3+4+5，12就是这样的数。
2=1+1，2不是这样的数，因为等号右边不是连续正数
给定一个参数N，返回是不是可以表示成若干连续正数和的数
#include <iostream>
using namespace std;
bool isMSum1(int num) {
for (int start = 1; start <= num; start++) {
int sum = start;
for (int j = start + 1; j <= num; j++) {
if (sum + j > num) {
break;
}
if (sum + j == num) {
return true;
}
sum += j;
}
}
return false;
}
bool isMSum2(int num) {
return (num & (num - 1)) != 0;
}
int main () {
for (int num = 1; num < 500; num++) {
if(isMSum1(num) != isMSum2(num))
cout << "oops" << endl;
}
return 0;
}
题目4：int[] d，d[i]：i号怪兽的能力
int[] p，p[i]：i号怪兽要求的钱
开始时你的能力是0，你的目标是从0号怪兽开始，通过所有的怪兽。
如果你当前的能力，小于i号怪兽的能力，你必须付出p[i]的钱，贿赂这个怪兽，然后怪兽就会加入你
他的能力直接累加到你的能力上；如果你当前的能力，大于等于i号怪兽的能力
你可以选择直接通过，你的能力并不会下降，你也可以选择贿赂这个怪兽，然后怪兽就会加入你
他的能力直接累加到你的能力上
返回通过所有的怪兽，需要花的最小钱数
解题提示：minMoney1的方法是在数据规模小的情况下的解法，minMoney2则是在p[i]钱数很大的情况下的解法。
#include <iostream>
#include <vector>
#include <time.h>
#include <stdlib.h>
using namespace std;
// 来到了当前位置index,当前的能力是ability, 如果要通过后续的怪兽，求最小的钱数。
int minMoney1(vector<int>& d, vector<int>& p,int index, int ability) {
if (index == d.size()) {
return 0;
}
// 能力足以通过
if(ability >= d[index]) {
return min(minMoney1(d, p, index + 1, ability), minMoney1(d, p, index + 1, ability + d[index]) + p[index]);
}
return minMoney1(d, p, index + 1, ability + d[index]) + p[index];
}
// 从0....index号怪兽，花的钱，必须严格==money
// 如果通过不了，返回-1
// 如果可以通过，返回能通过情况下的最大能力值
int process2(vector<int>& d, vector<int>& p,int index, int money) {
if(index == -1) {
return money == 0 ? 0 : -1;
}
int p1 = -1;
int preAbility = process2(d, p, index - 1, money);
if(preAbility != -1 && preAbility >= d[index]) {
p1 = preAbility;
}
int p2 = -1;
int preAbility2 = process2(d, p, index - 1, money - p[index]);
if(preAbility2 != -1) {
p2 = preAbility2 + d[index];
}
return max(p1, p2);
}
int minMoney2(vector<int>d, vector<int>p) {
int allMoney = 0;
int len = d.size();
for (int num : p)
{
allMoney += num;
}
for (int money = 0; money < allMoney; money++) {
if(process2(d,p,len-1,money) != -1) {
return money;
}
}
return allMoney;
}
vector<vector<int>> generateTwoRandomArray(int len, int value) {
int size = (rand() % len) + 1;
vector<vector<int>> arrs(2,vector<int>(size));
for (int i = 0; i < size; i++)
{
arrs[0][i] = (int)(rand()%value) + 1;
arrs[1][i] = (int)(rand()%value) + 1;
}
return arrs;
}
int main () {
srand((unsigned int)time(NULL));
int testTimes = 10000;
for (int i = 0; i < testTimes; i++)
{
vector<vector<int>> arr = generateTwoRandomArray(10, 20);
vector<int> d = arr[0];
vector<int> p = arr[1];
if(minMoney1(d,p,0,0) != minMoney2(d,p)) {
cout << "oops!" << endl;
break;
}
}
return 0;
}
