求 x * 99 + y * 199 最接近 1159 的 x、y 的组合

April · 2017-07-22 02:46:32 · 3128 次点击 · 大约8小时之前 开始浏览    置顶
这是一个创建于 2017-07-22 02:46:32 的主题,其中的信息可能已经有所发展或是发生改变。

求更好的实现方法,谢谢!

我这个写法实在是太烂了,求指点!谢谢!

###点我直接改代码

package main

import (
    "fmt"
    "sort"
)

func main() {
    sum := 1159
    res := make(map[int][]int)
    var fin []int
    for i := 0; i < 12; i++ {
        for j := 0; j < 6; j++ {
            tmp := sum - 99*i - 199*j
            if tmp > 0 && tmp < 100 {
                res[tmp] = []int{i, j}
                fin = append(fin, tmp)
            }
        }
    }
    sort.Ints(fin)
    fmt.Println(fin[0])
    fmt.Println(res[fin[0]])
}

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

3128 次点击  
加入收藏 微博
13 回复  |  直到 2017-07-25 10:45:19
sdvdxl
sdvdxl · #1 · 8年之前
package main

import (
    "fmt"
    "math"
)

func main() {
    sum := 1159
    a, b := 99, 199
    x, y := find(a, b, sum)
    result := a*x + b*y
    fmt.Println("x=", x, ", y=", y, ", 最接近的值为:", result, " 差值为:", math.Abs(float64(result-sum)))

}

func find(a, b, result int) (x, y int) {
    xx, yy := 0, 0
    for x := 0; ; x++ {
        for y := 0; ; y++ {
            if math.Abs(float64(a*x+b*y-result)) <= math.Abs(float64(a*xx+b*yy-result)) {
                xx = x
                yy = y
            } else {
                return xx, yy
            }
        }
    }
}
sdvdxl
sdvdxl · #2 · 8年之前

另外,你这个算法有问题,1和5的值为 99+5*199=1094,相差65,我这个算出的是: x= 0 , y= 6 , 最接近的值为: 1194 差值为: 35

April
April · #3 · 8年之前
sdvdxlsdvdxl #2 回复

另外,你这个算法有问题,1和5的值为 99+5*199=1094,相差65,我这个算出的是: x= 0 , y= 6 , 最接近的值为: 1194 差值为: 35

谢谢指出! 实际的需求是这样的,准备注销小招行的信用卡,但是信用卡中还有1159积分,刚好看到可以捐给 贫困/疾病/缺书 的孩子,为了获得最优比,就想这个用很少有机会使用的 go语言 来算一下,怎样才能充分利用这个积分,尽量少一点儿捐给银行!

所以,必须保证 最优比 的值,小于等于 1159

再次感谢您的回复和代码! 已认真阅读您的代码!谢谢!

April
April · #4 · 8年之前
sdvdxlsdvdxl #2 回复

另外,你这个算法有问题,1和5的值为 99+5*199=1094,相差65,我这个算出的是: x= 0 , y= 6 , 最接近的值为: 1194 差值为: 35

建议把 else 改用 continue

specita
specita · #5 · 8年之前

x99+199y = 100x+200y-(x+y) x+2相当于y+1 如果最终答案是需要result <= 1159的话 因为x<= 11,y<=5, 要让100x+200y=1100 and x+y最小 所以x+y最小的情况是y最大,即x=1,y=5

specita
specita · #6 · 8年之前
specitaspecita #5 回复

x*99+199*y = 100*x+200*y-(x+y) x+2相当于y+1 如果最终答案是需要result <= 1159的话 因为x<= 11,y<=5, 要让100*x+200*y=1100 and x+y最小 所以x+y最小的情况是y最大,即x=1,y=5

所以如果x99+y199这个公式固定且答案<=某个值

func find(result int) (int, int) {
    y := result / 200
    x := (result - y*200) / 100

    return x, y
}

如果公式不固定的话,那只能穷举了

April
April · #7 · 8年之前
specitaspecita #5 回复

x*99+199*y = 100*x+200*y-(x+y) x+2相当于y+1 如果最终答案是需要result <= 1159的话 因为x<= 11,y<=5, 要让100*x+200*y=1100 and x+y最小 所以x+y最小的情况是y最大,即x=1,y=5

非常感谢您的回复! 这个思路非常棒! 有两点不明白,请教您一下: 1.x+2 相当于 y+1 是如何得来的? 2.x+y 最小,是如何得来的?

想到以上这些的思路是什么? 觉得我自己在知识上有所欠缺,想不明白

期待回复,谢谢!

specita
specita · #8 · 8年之前
AprilApril #7 回复

#5楼 @specita 非常感谢您的回复! 这个思路非常棒! 有两点不明白,请教您一下: 1.x+2 相当于 y+1 是如何得来的? 2.x+y 最小,是如何得来的? 想到以上这些的思路是什么? 觉得我自己在知识上有所欠缺,想不明白 期待回复,谢谢!

都是基于100x+200y-(x+y)这个公式,200y/100x=2y/x,所以y/x=2/1,至于x+y最小,是因为100x+200y<=1159,x+y<11,那100x+200y=1100,所以要最接近1159,肯定x+y要最小,得到的结果才是最接近的。 这种算法只能基于你这种特定条件下才有效的,不能通用的。。

April
April · #9 · 8年之前
specitaspecita #8 回复

#7楼 @April 都是基于100x+200y-(x+y)这个公式,200y/100x=2y/x,所以y/x=2/1,至于x+y最小,是因为100x+200y<=1159,x+y<11,那100x+200y=1100,所以要最接近1159,肯定x+y要最小,得到的结果才是最接近的。 这种算法只能基于你这种特定条件下才有效的,不能通用的。。

学到了!非常感谢!

yikeso
yikeso · #10 · 8年之前

ax+by=c,这就是个斜线方程。xy如果是取float,根本就有无穷的解,只有当xy均为整数,且均大于0问题才成立。<br>

<p> func getXY(){<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp;x := 0<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp;a := 100<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp;b := 200<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp;c := 1159<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp;m := 1.0<br /> <span></span>&nbsp; &nbsp; &nbsp; min := float64(c)<br /> <span></span>&nbsp; &nbsp; &nbsp; r := [2]int{}<br /> <span></span>&nbsp; &nbsp; &nbsp; var d,e float64<br /> <span></span>&nbsp; &nbsp; &nbsp; for m &gt;= 0 {<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;m = float64(c - a x)/float64(b)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;d = math.Abs(float64(ax+bint(m)-c))<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;e = math.Abs(float64(ax+bint(m+1)-c))<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if d &gt; e{<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if e == 0{<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; fmt.Println("最小差值:",e)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; fmt.Println("xy取值:",r)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}else if e &lt; min{<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min = e<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; r[0] = x<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; r[1] = int(m+1)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}else {<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if d == 0{<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;r[0] = x<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;r[1] = int(m)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;fmt.Println("最小差值:",d)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;fmt.Println("xy取值:",r)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}else if d &lt; min{<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min = d<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; r[0] = x<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; r[1] = int(m)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;x++<br /> <span></span>&nbsp; &nbsp; &nbsp; }<br /> <span></span>&nbsp; &nbsp; &nbsp; y := 0<br /> <span></span>&nbsp; &nbsp; &nbsp; for m &gt;= 0 {<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;m = float64(c - b y)/float64(a)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;d = math.Abs(float64(by+aint(m)-c))<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;e = math.Abs(float64(by+aint(m+1)-c))<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if d &gt; e{<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if e == 0{<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;r[1] = y<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;r[0] = int(m+1)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;fmt.Println("最小差值:",e)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;fmt.Println("xy取值:",r)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }else if e &lt; min{<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;min = e<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;r[1] = y<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;r[0] = int(m+1)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }else {<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if d == 0{<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;r[1] = y<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;r[0] = int(m)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;fmt.Println("最小差值:",d)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;fmt.Println("xy取值:",r)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}else if d &lt; min{<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min = d<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; r[1] = y<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; r[0] = int(m)<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<br /> <span></span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;y++<br /> <span></span>&nbsp; &nbsp; &nbsp;}<br /> <span></span>&nbsp; &nbsp; &nbsp;fmt.Println("最小差值:",m)<br /> <span></span>&nbsp; &nbsp; &nbsp;fmt.Println("xy取值:",r)<br /> } </p> <div> <br /> </div> <p> <br /> </p>

sdvdxl
sdvdxl · #11 · 8年之前
AprilApril #4 回复

#2楼 @sdvdxl 建议把 else 改用 continue

也可以,加continue 是放在if里面,然后if下面直接return,效果一样,写法可能会好看一点?

April
April · #12 · 8年之前
sdvdxlsdvdxl #11 回复

#4楼 @April 也可以,加continue 是放在if里面,然后if下面直接return,效果一样,写法可能会好看一点?

嗯,写 php 代码的时候,phpmd 会建议使用 continue,而不是使用 else

April
April · #13 · 8年之前
yikesoyikeso #10 回复

ax+by=c,这就是个斜线方程。xy如果是取float,根本就有无穷的解,只有当xy均为整数,且均大于0问题才成立。

func getXY(){
       x := 0
       a := 100
       b := 200
       c := 1159
       m := 1.0
      min := float64(c)
      r := [2]int{}
      var d,e float64
      for m >= 0 {
           m = float64(c - a * x)/float64(b)
           d = math.Abs(float64(a*x+b*int(m)-c))
           e = math.Abs(float64(a*x+b*int(m+1)-c))
           if d > e{
                   if e == 0{
                          fmt.Println("最小差值:",e)
                          fmt.Println("xy取值:",r)
                          return
                   }else if e < min{
                          min = e
                          r[0] = x
                          r[1] = int(m+1)
                  }
           }else {
                  if d == 0{
                         r[0] = x
                         r[1] = int(m)
                         fmt.Println("最小差值:",d)
                         fmt.Println("xy取值:",r)
                         return
                 }else if d < min{
                        min = d
                        r[0] = x
                        r[1] = int(m)
                 }
           }
           x++
      }
      y := 0
      for m >= 0 {
           m = float64(c - b * y)/float64(a)
           d = math.Abs(float64(b*y+a*int(m)-c))
           e = math.Abs(float64(b*y+a*int(m+1)-c))
           if d > e{
                    if e == 0{
                             r[1] = y
                             r[0] = int(m+1)
                             fmt.Println("最小差值:",e)
                             fmt.Println("xy取值:",r)
                             return
                      }else if e < min{
                             min = e
                             r[1] = y
                             r[0] = int(m+1)
                       }
              }else {
                       if d == 0{
                             r[1] = y
                             r[0] = int(m)
                             fmt.Println("最小差值:",d)
                             fmt.Println("xy取值:",r)
                             return
               }else if d < min{
                          min = d
                          r[1] = y
                          r[0] = int(m)
                }
          }
           y++
     }
     fmt.Println("最小差值:",m)
     fmt.Println("xy取值:",r)
}



切线方程?

添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传