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语言题解 | 消失的数字&轮转数组
目录
相关文章
|
8月前
|
存储
【机组期末速成】计算机的运算方法|进制转换|无符号数与有符号数|数的定点表示与浮点表示|定点运算
【机组期末速成】计算机的运算方法|进制转换|无符号数与有符号数|数的定点表示与浮点表示|定点运算
196 0
|
C语言
C语言之回文数的求解。回文数一个5位数,判断它是不是回文数。即12321是回文数,个位与万位相同,十位与千位相同。
C语言之回文数的求解。回文数一个5位数,判断它是不是回文数。即12321是回文数,个位与万位相同,十位与千位相同。
200 0
|
7月前
1034 有理数四则运算 (20 分)
1034 有理数四则运算 (20 分)
【剑指offer】-数值的整数次方-12/67
【剑指offer】-数值的整数次方-12/67
【每周一坑】​正整数分解质因数 +【解答】计算100以内质数之和
关于分解质因数:每个合数都可以写成几个质数相乘的形式,其中每个质数都是这个合数的因数,把一个合数用质因数相乘的形式表示出来,叫做分解质因数。分解质因数只针对合数。
剑指offer 15. 数值的整数次方
剑指offer 15. 数值的整数次方
57 0
|
算法 前端开发 程序员
「LeetCode」剑指Offer-16数值的整数次方⚡️
「LeetCode」剑指Offer-16数值的整数次方⚡️
104 0
「LeetCode」剑指Offer-16数值的整数次方⚡️
|
算法
经典算法题-大数相加&数字字符串相加
leetcode:415. 字符串相加题链 这是一个校招面试时候,手写频率比较高的一个算法题,这里给大家分享三种方法: 一个常规解法,两个清奇的思路
|
存储 算法
LeetCode 02:“两数相加”,小学加法运算而已?
LeetCode 02:“两数相加”,小学加法运算而已?
127 0
LeetCode 02:“两数相加”,小学加法运算而已?
|
机器学习/深度学习 C语言
【C语言程序设计】~求两个整数之和
【C语言程序设计】~求两个整数之和
156 0