《算法竞赛·快冲300题》每日一题:“凑二十四”

这篇具有很好参考价值的文章主要介绍了《算法竞赛·快冲300题》每日一题:“凑二十四”。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法竞赛·快冲300题》将于2024年出版,是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。


凑二十四” ,链接: http://oj.ecustacm.cn/problem.php?id=1793

题目描述

【题目描述】 给你n个数字,你需要在n-1个间隔中添加符号+、-、×,按照正常优先级计算结果。请你输出有多少种方案,计算结果等于24。
【输入格式】 第一行为正整数n(2≤n≤10)。第二行n个正整数表示给定的n个数字,数字不超过50。
【输出格式】 输出一个数字表示答案。
【输入样例】

5
2 4 6 8 16

【输出样例】

2

题解

   如果尝试所有可能组合,共有多少种组合?最多n=10个数字时,需要添加9个符号,共 3 9 = 19683 3^9=19683 39=19683种组合,并不多。
  用DFS搜索所有可能组合。由于只有19683种情况,不用剪枝。
  代码用dfs()搜索所有符号组合。对每个组合,用check()检查计算结果是否等于24。先计算乘法,再计算加减。下面的代码用了简单直接的模拟法。先处理表达式中的乘法,对两个数做乘法时,把计算结果存在后面,前面置零,并把符号改为前面的加减,例如3+4×5,先处理乘法,转换为3+0+20。
  check()也有其他写法,例如先把表达式(称为中缀表达式)转为逆波兰表达式,然后用栈来计算逆波兰表达式。因为比较繁琐,这里没有给出代码。
【重点】 DFS 。文章来源地址https://www.toymoban.com/news/detail-669108.html

C++代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, a[11];
int op[11];               //第i个间隔的符号 + - * = 0 1 2
int ans;
ll check(){   //先计算*,再计算+-
    ll t[11] = {0}, t_op[11] = {0};
    for(int i=1; i<=n; i++)
        t[i] = a[i], t_op[i] = op[i];
    //先处理乘号:把乘积结果存入t[i+1]、t[i]设置为0、符号沿用前面的符号
    for(int i = 1; i < n; i++)
        if(t_op[i] == 2)
            t[i+1] *= t[i], t[i] = 0, t_op[i] = t_op[i-1];
    //最后加减
    ll sum = t[1];
    for(int i = 1; i < n; i++){
        if(t_op[i] == 0)  sum += t[i+1]; //加
        else sum -= t[i+1];              //减
    }
    return sum;
}
void dfs(int depth){
    if(depth == n){
        if(check() == 24)   ans++;
        return;
    }
    for(int i = 0; i <= 2; i++) {   //继续添加下一个符号
        op[depth] = i;
        dfs(depth + 1);
    }
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)    cin >> a[i];
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

Java代码

import java.util.Scanner;
public class Main {
    static int n, a[] = new int[11], op[] = new int[11]; // 第i个间隔的符号 + - * = 0 1 2
    static int ans;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        for (int i = 1; i <= n; i++)   a[i] = in.nextInt();
        dfs(1);
        System.out.println(ans);
        in.close();
    }
    static long check() { // 先计算*,再计算+-
        long[] t = new long[11];
        int[] t_op = new int[11];
        for (int i = 1; i <= n; i++) {
            t[i] = a[i];
            t_op[i] = op[i];
        }
        // 先处理乘号:把乘积结果存入t[i+1]、t[i]设置为0、符号沿用前面的符号
        for (int i = 1; i < n; i++) {
            if (t_op[i] == 2) {
                t[i + 1] *= t[i];
                t[i] = 0;
                t_op[i] = t_op[i - 1];
            }
        }
        // 最后加减
        long sum = t[1];
        for (int i = 1; i < n; i++) {
            if (t_op[i] == 0) sum += t[i + 1]; // 加
            else              sum -= t[i + 1]; // 减
        }
        return sum;
    }
    static void dfs(int depth) {
        if (depth == n) {
            if (check() == 24)   ans++;
            return;
        }
        for (int i = 0; i <= 2; i++) { // 继续添加下一个符号
            op[depth] = i;
            dfs(depth + 1);
        }
    }
}

Python代码

n = int(input())
a = [0]+list(map(int, input().split()))     #输入到a[1]-a[10]
op = [0] * 11                               # 第i个间隔的符号 + - * = 0 1 2
ans = 0
def check():# 先计算*,再计算+-
    t = [0] * 11
    t_op = [0] * 11
    for i in range(1, n+1):
        t[i] = a[i]
        t_op[i] = op[i]
    # 先处理乘号:把乘积结果存入t[i+1]、t[i]设置为0、符号沿用前面的符号
    for i in range(1, n):
        if t_op[i] == 2:
            t[i+1] *= t[i]
            t[i] = 0
            t_op[i] = t_op[i-1]
    # 最后加减
    sum = t[1]
    for i in range(1, n):
        if t_op[i] == 0: sum += t[i+1]  # 加
        else:            sum -= t[i+1]  # 减
    return sum
def dfs(depth):
    global ans
    if depth == n:
        if check() == 24:   ans += 1
        return
    for i in range(3):                  # 继续添加下一个符号
        op[depth] = i
        dfs(depth + 1)
dfs(1)
print(ans)

到了这里,关于《算法竞赛·快冲300题》每日一题:“凑二十四”的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《算法竞赛·快冲300题》每日一题:“松鼠与栗子”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 松鼠与栗子 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1852 【题目描述】 现在有m棵栗

    2024年02月11日
    浏览(43)
  • 罗勇军 → 《算法竞赛·快冲300题》每日一题:“排列变换” ← 贪心算法

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1812 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 给定一个长度为 n 的排列 a,需要将这个排列变成 b。 每次可以选择一个数字往左移若干个位置。 请求出 最小需要移动的元素个数 。 【输入格式】 第一行为正整数 n,1≤n≤100000。

    2024年02月12日
    浏览(40)
  • 罗勇军 →《算法竞赛·快冲300题》每日一题:“乘积” ← 动态规划

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1781 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 给你一个长度为 n 的序列,序列中的元素只包括 1 和 -1。 请问有多少个连续的子序列乘积为正数。 【输入格式】 输入第一行为正整数 n。(n不超过10^6) 第二行包含 n 个整数。 【输

    2024年02月11日
    浏览(49)
  • 罗勇军 →《算法竞赛·快冲300题》每日一题:“游泳” ← DFS+剪枝

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1753 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 游泳池可以等分为n行n列的小区域,每个区域的温度不同。 小明现在在要从游泳池的左上角(1, 1)游到右下角(n, n),小明只能向上下左右四个方向游,不能游出泳池。 而小明对温度十分

    2024年02月10日
    浏览(36)
  • 罗勇军 →《算法竞赛·快冲300题》每日一题:“小球配对” ← 并查集

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1850 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 给定 n 个小球,编号为 1-n ,给定 m 个篮子,编号为 1-m 。 每个球只允许放入样例给定的编号为 Ai 或者 Bi 的两个篮子中的 1 个。 每个球必须放入某个篮子。 如果篮子中球的数量为奇

    2024年02月11日
    浏览(39)
  • 算法|每日一题|H 指数|二分

    原题地址: 力扣每日一题:H 指数 给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义:h 代表“高引用次数” ,一名科研人员的 h 指数 是指他(她)至少发表了 h 篇论文,并且每

    2024年02月08日
    浏览(40)
  • 算法每日一题:赎金信 | 字符和整数

    hello,大家好,我是星恒 今天给大家带来的题目是一道简单题目,主要帮大家复习一下字符串和字符的相关操作 给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以,返回 true ;否则返回 false 。 magazine 中的每个字符只能在 ransom

    2024年01月21日
    浏览(43)
  • 每日一题之常见的排序算法

    排序是最常用的算法,常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、希尔排序和归并排序。除此之外,还有桶排序、堆排序、基数排序和计数排序。 1、冒泡排序 冒泡排序就是把小的元素往前放或大的元素往后放,比较的是相邻的两个元素。 时间复杂度:

    2024年02月13日
    浏览(39)
  • 算法与数据结构(二十四)最优子结构原理和 dp 数组遍历方向

    注:此文只在个人总结 labuladong 动态规划框架,仅限于学习交流,版权归原作者所有; 本文是两年前发的 动态规划答疑篇open in new window 的修订版,根据我的不断学习总结以及读者的评论反馈,我给扩展了更多内容,力求使本文成为继 动态规划核心套路框架 之后的一篇全面

    2024年02月12日
    浏览(34)
  • 【迎战蓝桥】 算法·每日一题(详解+多解)-- day5

    🤞目录🤞 💖1. 数组中出现次数超过一半的数字 💖2. 二进制中1的个数 💖3. 替换空格 【大家好,我是 爱干饭的猿 ,如果喜欢这篇文章, 点个赞 👍, 关注一下吧, 后续会一直分享题目与算法思路 】 描述 给一个长度为 n 的数组,数组中有一个数字出现的次数超过数组长

    2023年04月08日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包