文心一言 VS 讯飞星火 VS chatgpt （236）-- 算法导论17.3 2题

package main  
  
import (  
    "fmt"  
    "math"  
)  
  
// amortizedCost 计算第 i 个操作的摊还成本  
func amortizedCost(i int) int {  
    if i&(i-1) == 0 { // 判断 i 是否为 2 的幂  
        return i / 2 // 当 i 是 2 的幂时，摊还成本为 i/2  
    }  
    return 1 // 当 i 不是 2 的幂时，摊还成本为 1  
}  
  
func main() {  
    n := 10 // 假设操作序列有 10 个操作  
    for i := 1; i <= n; i++ {  
        cost := amortizedCost(i)  
        fmt.Printf("Operation %d has an amortized cost of %d\n", i, cost)  
    }  
}

package main
import (
    "fmt"
)
func amortizedCost(n int) float64 {
    cost := 0.0
    for i := 1; i <= n; i++ {
        if (i & (i - 1)) == 0 { // 判断i是否为2的幂
            cost += float64(i)
        } else {
            cost += 1.0
        }
    }
    return cost / float64(n)
}
func main() {
    fmt.Println(amortizedCost(10)) // 输出结果应为1.3899999999999999
}

package main

import (
    "fmt"
    "math"
)

func binarySearchInsertion(data []int, key int) {
    n := len(data)
    for i := 0; i < n; i++ {
        if key <= data[i] {
            data = append(data[:i], append([]int{key}, data[i:]...)...)
            break
        }
    }
}

func main() {
    data := []int{2, 4, 6, 8, 10}
    key := 5

    binarySearchInsertion(data, key)

    fmt.Println(data)
}

package main
import (
    "fmt"
)
// CalculateAggregateCost calculates the aggregate cost for each operation
func CalculateAggregateCost(n int) (aggregateCost float64) {
    // The formula for the aggregate cost is
    // s = Σ(i * (1 - 1/2^i)) for i from 1 to n
    // Since the problem specifies that i is strictly a power of 2,
    // we only sum from 1 to the highest power of 2 less than or equal to n
    // The sum is calculated using the formula for the sum of a geometric series
    // For our problem, the geometric series is (1 - 1/2^i)
    sum := 0.0
    powerOfTwo := 1
    for powerOfTwo <= n {
        sum += float64(powerOfTwo) * (1 - 1.0/float64(1<<powerOfTwo)) // 1<<powerOfTwo is 2^powerOfTwo
        powerOfTwo <<= 1 // equivalent to powerOfTwo *= 2
    }
    aggregateCost = sum
    return
}
func main() {
    n := 10 // Replace with the value of n for your problem
    cost := CalculateAggregateCost(n)
    fmt.Printf("The aggregate cost for each operation is: %v\n", cost)
}

package main

import (
    "fmt"
    "math"
)

func main() {
    n := 100 // 操作序列的长度
    data := []int{} // 数据结构

    phi := func(i int) int { // 定义势函数
        return len(data)
    }

    for i := 1; i <= n; i++ {
        if isPowerOfTwo(i) {
            ci := i + 1 - phi(i-1)
            fmt.Printf("第 %d 个操作的实际代价：%d\n", i, ci)
        } else {
            ci := 1 - phi(i-1)
            fmt.Printf("第 %d 个操作的实际代价：%d\n", i, ci)
        }
        
        data = append(data, i) // 模拟插入元素到数据结构中
    }
}

func isPowerOfTwo(num int) bool { // 判断一个数是否为2的幂次方
    return num > 0 && (num & (num - 1)) == 0
}

package main

import (
    "fmt"
)

// Operation 表示操作序列中的单个操作
type Operation int

// Cost 计算操作的代价
func (op Operation) Cost() int {
    if op == 0 {
        return 1
    }
    return int(op)
}

// AmortizedCost 使用势能法计算操作的摊还代价
func AmortizedCost(op Operation, potential *int) int {
    cost := op.Cost()
    // 如果操作代价为 1，增加势能
    if cost == 1 {
        *potential++
    } else {
        // 否则，减少势能并计算摊还代价
        amortizedCost := *potential + cost
        *potential -= cost - 1
    }
    return amortizedCost
}

func main() {
    n := 10 // 假设操作序列的长度为 10
    potential := 0 // 初始化势能为 0

    // 模拟操作序列
    for i := 1; i <= n; i++ {
        // 如果 i 是 2 的幂，则创建一个代价为 i 的操作
        if i&(i-1) == 0 {
            op := Operation(i)
            fmt.Printf("Operation %d has a cost of %d and an amortized cost of %d\n", i, op.Cost(), AmortizedCost(op, &potential))
        } else {
            // 否则，创建一个代价为 1 的操作
            op := Operation(1)
            fmt.Printf("Operation %d has a cost of %d and an amortized cost of %d\n", i, op.Cost(), AmortizedCost(op, &potential))
        }
    }
}

package main

import (
    "fmt"
    "math"
)

func main() {
    n := 10
    potential := 0.0
    amortizedCosts := make([]float64, n)

    for i := 1; i <= n; i++ {
        potentialChange := 0.0
        if isPowerOfTwo(i) {
            potentialChange = float64(i) - potential
        } else {
            potentialChange = 1.0 - potential
        }
        amortizedCost := potentialChange / float64(i)
        amortizedCosts[i-1] = amortizedCost
        potential += potentialChange
    }

    fmt.Println("Amortized costs:", amortizedCosts)
}

func isPowerOfTwo(n int) bool {
    return n != 0 && (n&(n-1)) == 0
}