我正在使用Go进行Project Euler的问题22,我是新手,我的代码给出了不一致的结果,这意味着每次运行程序时它都会显示不同的结果.它总是非常接近我所看到的正确答案,但范围在几百点之内.我原本以为它可能是由于浮动舍入不准确但我已经检查过,事实并非如此(我认为).
如果有人能够指出可能导致这种情况发生的事情,我将非常感激.我已经努力在几天内找到我的代码问题而无法解决它甚至在论坛上发现类似的问题.
作为旁注,我最初使用golang数学/大包编写了这个,并获得了相同的更改结果.
如果有人能够指出可能导致这种情况发生的事情,我将非常感激.我已经努力在几天内找到我的代码问题而无法解决它甚至在论坛上发现类似的问题.
作为旁注,我最初使用golang数学/大包编写了这个,并获得了相同的更改结果.
package main
import (
"fmt"
"io/IoUtil"
"log"
"math"
"strings"
)
func openFileReturnSlice(f string) []string {
bytes,err := IoUtil.ReadFile(f)
if err != nil {
log.Fatal("Failed to read file: p022_names.txt")
}
s2s := strings.Split(string(bytes),"\"")
s22 := strings.Join(s2s,"")
names := strings.Split(s22,",")
return names
}
func alphabetize(n []string) ([]string,map[string]int) {
wordsValues := make(map[string]float64)
wordLetterVal := make(map[string]int)
for _,s := range n {
loop := -1
var wordValue float64
alpha := int(0)
for _,l := range s {
ell := int(l) - 64
mvDec := math.Pow(100,math.Abs(float64(loop)))
wordValue += float64(l) / mvDec
alpha += ell
loop--
}
wordsValues[s] = wordValue
wordLetterVal[s] = alpha
}
var sortedNames []string
lenWordValues := len(wordsValues)
for i := 0; i < lenWordValues; i++ {
var lowValName string
lowVal := float64(10)
for k,v := range wordsValues {
if v < lowVal {
lowVal = v
lowValName = k
}
}
delete(wordsValues,lowValName)
sortedNames = append(sortedNames,lowValName)
}
return sortedNames,wordLetterVal
}
func main() {
names := openFileReturnSlice("p022_names.txt")
alphabetical,sumAlphaValues := alphabetize(names)
var total int
for k := 0; k < len(alphabetical); k++ {
var temp int
key := k + 1
temp = sumAlphaValues[alphabetical[k]] * key
total += temp
}
fmt.Println("The total is: ",total)
}
使用浮点是可疑的,这是不精确的.未指定地图上的迭代顺序,并且不保证从一次迭代到下一次迭代是相同的.您对地图的使用是看似随机行为的最可能解释.
要问的第一个问题是：什么是正确的答案？
package main
import (
"bytes"
"fmt"
"io/IoUtil"
"log"
"strings"
)
func readNames(f string) []string {
b,err := IoUtil.ReadFile(f)
if err != nil {
log.Fatal(err)
}
s := string(bytes.Replace(b,[]byte(`"`),[]byte(``),-1))
return strings.Split(s,")
}
func totalscores(names []string) int64 {
for i := 0; i < len(names); i++ {
for j := i + 1; j < len(names); j++ {
if names[i] > names[j] {
names[i],names[j] = names[j],names[i]
}
}
}
total := int64(0)
for i,name := range names {
score := int64(0)
for _,char := range name {
score += int64(char - 'A' + 1)
}
score *= int64(i) + 1
total += score
}
return total
}
func main() {
names := readNames("p022_names.txt")
total := totalscores(names)
fmt.Println("The total is: ",total)
}
输出：
The total is: 871198282
这就是Project Euler期望您编写解决方案的第一个版本的方式.你的第二个版本应该用更快的排序替换简单的选择排序,比如Quicksort.
例如,您的程序需要很长时间才能产生错误的结果：
The total is: 871197995 real 0m1.945s user 0m1.944s sys 0m0.004s
我的程序生成正确的结果并且速度更快：
The total is: 871198282 real 0m0.771s user 0m0.768s sys 0m0.004s
如果我们用Go排序替换我的选择排序：
sort.StringSlice(names).Sort()
修改后的程序产生了正确的结果,速度更快：
The total is: 871198282 real 0m0.014s user 0m0.012s sys 0m0.000s
项目欧拉,名称得分,问题22是关于快速排序算法,而不是关于分数的微不足道的计算.
要获得代码的稳定结果,请注释掉delete语句：
// delete(wordsValues,lowValName)
现在您将遇到浮点错误：Floating-point arithmetic和IEEE floating point.
您的算法创建近似的,非唯一的浮点wordValues.因此,地图上的随机迭代可以选择一些不同的lowVal和lowValName对,并且可以删除不同的映射条目.
非唯一的单词值：
0.657666698284738 0.6576697465786885 0.6576697465786885 0.6576698865786884 0.6578786577658275 0.6578847978698485 0.658571858384738 0.6669827865826875 0.6765847269827377 0.676976698384738 0.677282738384698 0.6772827383847367 0.6772827383847367 0.677282738384738 0.677282738384738 0.6772827383847982 0.6776697769788476 0.6982786983847379 0.6986657871697675 0.7076798269786776 0.7076798269788476 0.7082657867698368 0.7082657867738368 0.7082696869827366 0.7082696869827366 0.7165668273697676 0.716979827169658 0.7169798271698486 0.716979827173658 0.716979827173658 0.716979827173658 0.7185737676698277 0.7269788273698486 0.7273766869716582 0.7465678185697674 0.746567818569769 0.746567818569769 0.7469657878698486 0.7479836980727379 0.7565847265827377 0.7565847269827377 0.7573776669827669 0.7765716865766978 0.7765826769767379 0.7765826769767379 0.7765827165826985 0.7765827165826985 0.7765827165826985 0.7765827165826985 0.7765827165827385 0.7765827165827385 0.7765827185698275 0.7773677269767378 0.827983657673787 0.8384698072657875 0.8472797765837379 0.8665766978847378
