Day4 计算糖果、进制转换

简介: Day4 计算糖果、进制转换

选择题

1.C函数

题目:下列程序执行后,输出的结果为()

#include <stdio.h>
int cnt = 0;
int fib(int n) 
{
    cnt++;
    if (n == 0)
        return 1;
    else if (n == 1)
        return 2;
    else
        return fib(n - 1) + fib(n - 2);
}
void main() 
{
    fib(8);
    printf("%d", cnt);
}


选项:

  • A、41
  • B、67
  • C、109
  • D、177

分析:该题考的是 斐波那契数列 相关知识:f(n) = f(n - 1) + f(n - 2)n > 0f(1) = 1f(2) = 2),递归求某个斐波那契数值,累计创建了多少层栈帧,具体可以看下图

最终计算得出 67

在涉及递归相关的问题时,可以尝试画出递归展开图,并且涉及重复的递归部分不必画出来,比如本题中的右半部分,可以复用左半部分回归的结果

结果:B


编程题

1.计算糖果

题目链接:计算糖果

题目分析:纯数学逻辑题了,可以根据条件可知:x1 = A - Bx2 = B - Cx3 = A+ Bx4 = B+ C,稍微运用一点等价计算,可以得出:A = x1 + BB = (x3 - x1) / 2C = x4 - B

接下来就很简单了,直接根据推导公式,编写程序即可

#include <iostream>
using namespace std;
//A = x1 + B
//B = (x3 - x1) / 2
//C = x4 - B
int main() 
{
    int x1, x2, x3, x4;
    cin >> x1 >> x2 >> x3 >> x4;
    int A, B, C;
    B = (x3 - x1) / 2;
    A = x1 + B;
    C = x4 - B;
    //需要进行合法性检测
    if(x1 == A - B && x2 == B - C && x3 == A + B && x4 == B + C)
        cout << A << " " << B << " " << C << endl;
    else
     cout << "No" << endl;
    return 0;
}


注意:因为存在不合法的情况,所以需要进行合法性检验,简单,对着题目要求判断一下所求值就好了

2.进制转换

题目链接:进制转换

题目分析:进制转换是程序员的必备技能,这题可以说是相当经典了。给定一个十进制数 M,再给出一个进制数 N,要求将 M 转为 N 进制数,比如十进制数 10,转为 2 进制表示为 1010,转为 8 进制为 12,转为 16 进制为 a,下面来看看具体代码实现

10 如何使用 2 进制表示?

  • 假设十进制数为 val,目标值为 target
  • 10 % 2 = 0,此时 val = 5 = (10 / 2)target = 0
  • 5 % 2 = 1,此时 val = 2 = (5 / 2)target = 10 = 1 + 0
  • 2 % 2 = 0,此时 val = 1 = (2 / 2)target = 010 = 0 + 10
  • 1 % 2 = 1,此时 val = 0 = (1 / 2)target = 1010 = 1 + 010

val 等于 0 时,进制转换就结束了

这里编写时用到了一个技巧:倒着转换,等转换完成后,再逆置,就是结果

这样做的好处是省去了很多麻烦,直接尾插即可

  • 不然得头插,挺麻烦的,效率也比较低
class Solution {
public:
    string solve(int M, int N) 
    {
        //所求值数组
        vector<int> solveVal = {'0', '1', '2', '3', '4', '5', '6', '7', '8',
                                '9', 'A', 'B', 'C', 'D', 'E', 'F'};
        int val = M;
        int base = N;   //进制数
        //需要先判断是否为负数
        bool flag = false;
        if(val < 0)
        {
            val *= -1;  //转为正数计算
            flag = true;
        }
        string target;  //所求目标值
        while(val)
        {
            target += solveVal[val % base];
            val /= base;
        }
        if(flag)
            target += '-';  //需要注意负号
        reverse(target.begin(), target.end());  //逆置
        return target;
    }
};


注意: 十六进制中,字母为大写,并且给出的十进制数 M 有可能为负数,假设为负数,需要标记一下,并在转换完成后,把 - 加上

选择题需要自己尝试画出递归展开图,这样才能领悟递归的真谛;两道编程题都是水题,但进制转换的思想值得学习,真正麻烦的进制转换是 M 进制数,转为 N 进制数,此时不是常规的十进制,因此再计算时,还需要设计对应的进制转换算法



相关文章推荐


Day3 字符串中找出连续最长的数字串、数组中出现次数超过一半的数字


Day2 排序子序列、倒置字符串


Day1 组队竞赛、删除公共字符


C++题解 | 逆波兰表达式相关


C语言题解 | 去重数组&&合并数组


C语言题解 | 消失的数字&轮转数组
目录
相关文章
|
6月前
|
算法
【一刷《剑指Offer》】面试题 11:数值的整数次方
【一刷《剑指Offer》】面试题 11:数值的整数次方
|
6月前
11.09作业详解(弹球距离,素数,最大公约数最小公倍数,求整数位数及其各位数字之和,打印乘法表)
11.09作业详解(弹球距离,素数,最大公约数最小公倍数,求整数位数及其各位数字之和,打印乘法表)
【剑指offer】-数值的整数次方-12/67
【剑指offer】-数值的整数次方-12/67
【每周一坑】​正整数分解质因数 +【解答】计算100以内质数之和
关于分解质因数:每个合数都可以写成几个质数相乘的形式,其中每个质数都是这个合数的因数,把一个合数用质因数相乘的形式表示出来,叫做分解质因数。分解质因数只针对合数。
|
算法
剑指Offer - 面试题16:数值的整数次方
剑指Offer - 面试题16:数值的整数次方
56 0
剑指offer 15. 数值的整数次方
剑指offer 15. 数值的整数次方
52 0
|
算法 C++ Python
每日算法系列【LeetCode 357】计算各个位数不同的数字个数
每日算法系列【LeetCode 357】计算各个位数不同的数字个数
【剑指offer】二进制中1的个数&&2的幂
【剑指offer】二进制中1的个数&&2的幂
【剑指offer】二进制中1的个数&&2的幂
leetcode-829. 连续整数求和(数论)
这题求连续正整数,刚好满足等差数列,可以用等差数列求和公式 n = (i + (i + k)) * (k + 1) / 2 其中i是连续正整数的首项,k是尾项和首项的差值
117 0
leetcode-829. 连续整数求和(数论)
7-41 大数的乘法 (10 分)
7-41 大数的乘法 (10 分)
79 0