2023-05-25：給定一個(gè)正整數(shù) x，我們將會(huì)寫出一個(gè)形如 x (op1) x (op2) x (op3) x ... 的表達(dá)式

其中每個(gè)運(yùn)算符 op1，op2，… 可以是加、減、乘、除之一

例如，對(duì)于 x = 3，我們可以寫出表達(dá)式 3 * 3 / 3 + 3 - 3，該式的值為3

在寫這樣的表達(dá)式時(shí)，我們需要遵守下面的慣例：

除運(yùn)算符（/）返回有理數(shù)

任何地方都沒有括號(hào)

我們使用通常的操作順序：乘法和除法發(fā)生在加法和減法之前

不允許使用一元否定運(yùn)算符（-）。例如，“x - x” 是一個(gè)有效的表達(dá)

因?yàn)樗皇褂脺p法，但是 “-x + x” 不是，因?yàn)樗褂昧朔穸ㄟ\(yùn)算符

我們希望編寫一個(gè)能使表達(dá)式等于給定的目標(biāo)值 target 且運(yùn)算符最少的表達(dá)式。

返回所用運(yùn)算符的最少數(shù)量。

輸入：x = 5, target = 501。

輸出：8。

答案2023-05-25：

大體過程如下：

1.定義函數(shù) leastOpsExpressTarget，傳入?yún)?shù) x 和 target。

2.初始化一個(gè) map 類型的變量 dp，用于記錄已經(jīng)計(jì)算過的結(jié)果。

3.調(diào)用函數(shù) dpf，傳入?yún)?shù) 0、target、x 和 dp。函數(shù) dpf 的作用是計(jì)算在當(dāng)前情況下，target 最少需要幾個(gè)運(yùn)算符才能被表達(dá)出來。

4.在函數(shù) dpf 中，首先判斷當(dāng)前情況是否已經(jīng)計(jì)算過，如果已經(jīng)計(jì)算過則直接返回結(jié)果。

5.如果沒有計(jì)算過，則根據(jù)題目要求，最多只能使用 x 的 i 次方來進(jìn)行運(yùn)算，所以需要記錄當(dāng)前來到了 x 的 i 次方這個(gè)數(shù)字。

6.如果 target 大于 0 且 i 小于 39（為了防止溢出），則根據(jù)題目要求，將 target 分解成商和余數(shù)兩部分，然后分別計(jì)算用加、減、乘、除運(yùn)算符可以得到的最小的運(yùn)算次數(shù)。

7.最后，將計(jì)算出的結(jié)果保存到 dp 中，并返回該結(jié)果。

8.定義函數(shù) cost，傳入?yún)?shù) i，用于得到 x 的 i 次方這個(gè)數(shù)字需要幾個(gè)運(yùn)算符，默認(rèn)前面再加個(gè)'+'或'-'。

9.定義函數(shù) min，傳入?yún)?shù) a 和 b，用于比較 a 和 b 的大小，并返回較小的值。

10.在主函數(shù) main 中，定義變量 x 和 target，分別賦值為 5 和 501。然后調(diào)用函數(shù) leastOpsExpressTarget，并將結(jié)果輸出。

時(shí)間復(fù)雜度：

• 函數(shù) leastOpsExpressTarget 中調(diào)用了函數(shù) dpf，而函數(shù) dpf 的時(shí)間復(fù)雜度為 O(log(target))（因?yàn)?i 最大可以達(dá)到 39，x^39 已經(jīng)大于等于 target），所以最終的時(shí)間復(fù)雜度為 O(log(target))。

空間復(fù)雜度：

• 函數(shù) leastOpsExpressTarget 中創(chuàng)建了一個(gè) map 類型的變量 dp，其中存儲(chǔ)的元素個(gè)數(shù)最多為 O(log(target) * 40)，所以空間復(fù)雜度為 O(log(target))。

go完整代碼如下：

package main

import (
	"fmt"
)

func leastOpsExpressTarget(x, target int) int {
	dp := make(map[int]map[int]int)
	return dpf(0, target, x, dp) - 1
}

// i : 當(dāng)前來到了x的i次方
// target : 認(rèn)為target只能由x的i次方，或者更高次方來解決，不能使用更低次方！
// 返回在這樣的情況下，target最少能由幾個(gè)運(yùn)算符搞定！
// (3, 1001231) -> 返回值！
// dp.get(3) -> {1001231 對(duì)應(yīng)的value}
func dpf(i, target, x int, dp map[int]map[int]int) int {
	if val, ok := dp[i][target]; ok {
		return val
	}

	ans := 0
	if target > 0 && i < 39 {
		if target == 1 {
			ans = cost(i)
		} else {
			div := target / x
			mod := target % x
			p1 := mod*cost(i) + dpf(i+1, div, x, dp)
			p2 := (x-mod)*cost(i) + dpf(i+1, div+1, x, dp)
			ans = min(p1, p2)
		}
	}
	if _, ok := dp[i]; !ok {
		dp[i] = make(map[int]int)
	}
	dp[i][target] = ans
	return ans
}

// 得到x的i次方這個(gè)數(shù)字
// 需要幾個(gè)運(yùn)算符，默認(rèn)前面再加個(gè)'+'或'-'
func cost(i int) int {
	if i == 0 {
		return 2
	}
	return i
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	x := 5
	target := 501
	fmt.Println(leastOpsExpressTarget(x, target))
}

rust完整代碼如下：

use std::collections::HashMap;

fn least_ops_express_target(x: i32, target: i32) -> i32 {
    let mut dp: HashMap<i32, HashMap<i32, i32>> = HashMap::new();
    dpf(0, target, x, &mut dp) - 1
}

// i : 當(dāng)前來到了x的i次方
// target : 認(rèn)為target只能由x的i次方，或者更高次方來解決，不能使用更低次方！
// 返回在這樣的情況下，target最少能由幾個(gè)運(yùn)算符搞定！
// (3, 1001231) -> 返回值！
// dp.get(3) -> {1001231 對(duì)應(yīng)的value}
fn dpf(i: i32, target: i32, x: i32, dp: &mut HashMap<i32, HashMap<i32, i32>>) -> i32 {
    if let Some(map) = dp.get(&i) {
        if let Some(val) = map.get(&target) {
            return *val;
        }
    }

    let ans: i32;
    if target > 0 && i < 39 {
        if target == 1 {
            ans = cost(i);
        } else {
            let div = target / x;
            let mod0 = target % x;
            let p1 = mod0 * cost(i) + dpf(i + 1, div, x, dp);
            let p2 = (x - mod0) * cost(i) + dpf(i + 1, div + 1, x, dp);
            ans = p1.min(p2);
        }
    } else {
        ans = 0;
    }

    dp.entry(i).or_insert(HashMap::new()).insert(target, ans);
    ans
}

// 得到x的i次方這個(gè)數(shù)字
// 需要幾個(gè)運(yùn)算符，默認(rèn)前面再加個(gè)'+'或'-'
fn cost(i: i32) -> i32 {
    if i == 0 {
        2
    } else {
        i
    }
}

fn main() {
    let x = 3;
    let target = 19;
    println!("{}", least_ops_express_target(x, target));

    let x = 5;
    let target = 501;
    println!("{}", least_ops_express_target(x, target));

    let x = 100;
    let target = 100000000;
    println!("{}", least_ops_express_target(x, target));
}

c語言完整代碼如下：

#include <stdio.h>
#include <stdlib.h>

int leastOpsExpressTarget(int x, int target);
int cost(int i);

int dpf(int i, int target, int x, int*** dp) {
    if (dp[i][target] != 0) {
        return dp[i][target];
    }

    int ans = 0;
    if (target > 0 && i < 39) {
        if (target == 1) {
            ans = cost(i);
        }
        else {
            int div = target / x;
            int mod = target % x;
            int p1 = mod * cost(i) + dpf(i + 1, div, x, dp);
            int p2 = (x - mod) * cost(i) + dpf(i + 1, div + 1, x, dp);
            ans = p1 < p2 ? p1 : p2;
        }
    }
    dp[i][target] = ans;
    return ans;
}

int leastOpsExpressTarget(int x, int target) {
    int** dp = (int**)calloc(40, sizeof(int*));
    for (int i = 0; i < 40; ++i) {
        dp[i] = (int*)calloc(target + 1, sizeof(int));
    }
    int ans = dpf(0, target, x, dp) - 1;
    for (int i = 0; i < 40; ++i) {
        free(dp[i]);
    }
    free(dp);
    return ans;
}

// 得到x的i次方這個(gè)數(shù)字
// 需要幾個(gè)運(yùn)算符，默認(rèn)前面再加個(gè)'+'或'-'
int cost(int i) {
    return i == 0 ? 2 : i;
}

int main() {
    int x = 5;
    int target = 501;
    printf("%d\n", leastOpsExpressTarget(x, target));
    return 0;
}

c++完整代碼如下：

#include <iostream>
#include <unordered_map>

using namespace std;

int cost(int i);

int dpf(int i, int target, int x, unordered_map<int, unordered_map<int, int>>& dp) {
    if (dp.count(i) && dp[i].count(target)) {
        return dp[i][target];
    }

    int ans = 0;
    if (target > 0 && i < 39) {
        if (target == 1) {
            ans = cost(i);
        }
        else {
            int div = target / x;
            int mod = target % x;
            int p1 = mod * cost(i) + dpf(i + 1, div, x, dp);
            int p2 = (x - mod) * cost(i) + dpf(i + 1, div + 1, x, dp);
            ans = min(p1, p2);
        }
    }
    if (!dp.count(i)) {
        dp[i] = unordered_map<int, int>();
    }
    dp[i][target] = ans;
    return ans;
}

int leastOpsExpressTarget(int x, int target) {
    unordered_map<int, unordered_map<int, int>> dp;
    return dpf(0, target, x, dp) - 1;
}

// 得到x的i次方這個(gè)數(shù)字
// 需要幾個(gè)運(yùn)算符，默認(rèn)前面再加個(gè)'+'或'-'
int cost(int i) {
    return i == 0 ? 2 : i;
}

int main() {
    int x = 5;
    int target = 501;
    cout << leastOpsExpressTarget(x, target) << endl;
    return 0;
}

文章來源地址http://www.zghlxwxcb.cn/news/detail-458989.html

到了這里，關(guān)于2023-05-25：給定一個(gè)正整數(shù) x，我們將會(huì)寫出一個(gè)形如 x (op1) x (op2) x (op3) x ... 的表達(dá)式 其中每個(gè)運(yùn)算符 op1，op2，… 可以是加、減、乘、除之一 例如的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！