算法：用5,7,12加减运算，求最少步数得到任意数n

sflyingdream 2011-06-21 09:44:01
加精
rt
...全文
2674 80 打赏 收藏 转发到动态 举报
写回复
用AI写文章
80 条回复
切换为时间正序
请发表友善的回复…
发表回复
fairywell 2011-08-24
  • 打赏
  • 举报
 回复
[Quote=引用 21 楼 gogdizzy 的回复:]

O(1)时间复杂度。

C/C++ code

/**
* 用5,7,12加减运算，最少步骤到大n
* gogdizzy@gmail.com
*/

#include <stdio.h>

#define abs(x) \
( (x^(x>>31))-(x>>31) )

int min_step( int N )
{
int diff;
int n5, n7, n……
[/Quote]
这程序是正解，赞一个！
Relict 2011-06-29
  • 打赏
  • 举报
 回复
4#+9#
jin225 2011-06-29
  • 打赏
  • 举报
 回复
复习了一下算法
WayneXuan 2011-06-29
  • 打赏
  • 举报
 回复
可以照一楼的方法做一做
cloudwu007 2011-06-29
  • 打赏
  • 举报
 回复
多谢提醒，看来还比较复杂。

[Quote=引用 73 楼 gogdizzy 的回复:]

#66的算法有问题。

54 = +6 x 5 +0 x 7 +2 x 12

而实际最小步骤应该是
54 = (0) * 5 + (6) * 7 + (1) * 12

引用 66 楼 cloudwu007 的回复:
-----------------Python code-------------------------

def getMinStep(N):
k=in……
[/Quote]
jim-single 2011-06-28
  • 打赏
  • 举报
 回复
路过，　学习

simple_blue 2011-06-28
  • 打赏
  • 举报
 回复
[Quote=引用 27 楼 kerbcurb 的回复:]

i, j, k 整数，可正负

5 * i + 7 * j + 12 * k = n;
|i| + |j| + |k| = 最小
[/Quote]

这个东西像不像拉格朗日乘数法求条件极值的问题？
天下第一好大人 2011-06-28
  • 打赏
  • 举报
 回复
#66的算法有问题。

54 = +6 x 5 +0 x 7 +2 x 12

而实际最小步骤应该是
54 = (0) * 5 + (6) * 7 + (1) * 12

[Quote=引用 66 楼 cloudwu007 的回复:]
-----------------Python code-------------------------

def getMinStep(N):
k=int(N / 12)
left=N-k*12
j=int(left/7)
left=left-j*7
i=int(left/5)
left=left-i*5
if(left < 0):
i-=v……
[/Quote]
hp3030_394844420 2011-06-28
  • 打赏
  • 举报
 回复
来学习的
wae_gossip 2011-06-27
  • 打赏
  • 举报
 回复
1.尽量用12应该是比较少的步数。
2.先用N/12得到余数k，然后用5，7,12组合得到k,如果k的解法中出现了-12，则与前的12对消，就得到结果
lz3771 2011-06-27
  • 打赏
  • 举报
 回复
学习了
seqingzi 2011-06-27
  • 打赏
  • 举报
 回复
[Quote=引用 40 楼 lisunlin0 的回复:]

引用 lisunlin0 的博客:
有同学面试的时候遇到要求一个数以最少步骤分解为另外两个数和差问题的解决，大约描述是“将一个数分解为几个数的和或者差的形式，并且使步骤最小”。

这类题的解题理论是数论里面的一次不定方程的整数解。
引用 百度百科:
定义1. 形如 ax + by = c ( a，b，c∈Z，a，b不同时为零)的方程称为二元一次不定方程。
定理1. 方程 ax + b……
[/Quote]

学习好信安数基的重要性...以前学过,现在忘了.看了你的才想起来.
tangkun323 2011-06-27
  • 打赏
  • 举报
 回复
不懂啊
zlcp520 2011-06-27
  • 打赏
  • 举报
 回复
内容存入剪贴板
friskit 2011-06-27
  • 打赏
  • 举报
 回复
学习了mark up
a1097593402 2011-06-27
  • 打赏
  • 举报
 回复
也没什么思路
yuyiran_1989 2011-06-27
  • 打赏
  • 举报
 回复
题意都没说清楚，当然各有各的做法了。
555555555555555 2011-06-27
  • 打赏
  • 举报
 回复
这种帖子能上首页
cloudwu007 2011-06-27
  • 打赏
  • 举报
 回复
-----------------Python code-------------------------

def getMinStep(N):
k=int(N / 12)
left=N-k*12
j=int(left/7)
left=left-j*7
i=int(left/5)
left=left-i*5
if(left < 0):
i-=val_0_11[-left][0];
j-=val_0_11[-left][1];
k-=val_0_11[-left][2];
else:
i+=val_0_11[left][0];
j+=val_0_11[left][1];
k+=val_0_11[left][2];
if(i > 0 and j > 0) or (i <0 and j<0): #Merge to 12
merge12=min(abs(i),abs(j))
if i>0:
i-=merge12
j-=merge12
k+=merge12
else:
i+=merge12
j+=merge12
k-=merge12
elif (i * k < 0):
merge7=min(abs(i),abs(k))
if i>0:
i-=merge7
j-=merge7
k+=merge7
else:
i+=merge7
j+=merge7
k-=merge7
elif (j * k < 0):
merge5=min(abs(j),abs(k))
if j>0:
i-=merge5
j-=merge5
k+=merge5
else:
i+=merge5
j+=merge5
k-=merge5

print("%d \t = %+d x 5 \t %+d x 7 \t %+d x 12"%(N,i,j,k))

return (i,j,k)


-100 = +0 x 5 -4 x 7 -6 x 12
-99 = -3 x 5 +0 x 7 -7 x 12
-98 = +0 x 5 -2 x 7 -7 x 12
-97 = -5 x 5 +0 x 7 -6 x 12
-96 = +0 x 5 +0 x 7 -8 x 12
-95 = +0 x 5 -5 x 7 -5 x 12
-94 = -2 x 5 +0 x 7 -7 x 12
-93 = +0 x 5 -3 x 7 -6 x 12
-92 = -4 x 5 +0 x 7 -6 x 12
-91 = +0 x 5 -1 x 7 -7 x 12
-90 = -6 x 5 +0 x 7 -5 x 12
-89 = -1 x 5 +0 x 7 -7 x 12
-88 = +0 x 5 -4 x 7 -5 x 12
-87 = -3 x 5 +0 x 7 -6 x 12
-86 = +0 x 5 -2 x 7 -6 x 12
-85 = -5 x 5 +0 x 7 -5 x 12
-84 = +0 x 5 +0 x 7 -7 x 12
-83 = +0 x 5 -5 x 7 -4 x 12
-82 = -2 x 5 +0 x 7 -6 x 12
-81 = +0 x 5 -3 x 7 -5 x 12
-80 = -4 x 5 +0 x 7 -5 x 12
-79 = +0 x 5 -1 x 7 -6 x 12
-78 = -6 x 5 +0 x 7 -4 x 12
-77 = -1 x 5 +0 x 7 -6 x 12
-76 = +0 x 5 -4 x 7 -4 x 12
-75 = -3 x 5 +0 x 7 -5 x 12
-74 = +0 x 5 -2 x 7 -5 x 12
-73 = -5 x 5 +0 x 7 -4 x 12
-72 = +0 x 5 +0 x 7 -6 x 12
-71 = +0 x 5 -5 x 7 -3 x 12
-70 = -2 x 5 +0 x 7 -5 x 12
-69 = +0 x 5 -3 x 7 -4 x 12
-68 = -4 x 5 +0 x 7 -4 x 12
-67 = +0 x 5 -1 x 7 -5 x 12
-66 = -6 x 5 +0 x 7 -3 x 12
-65 = -1 x 5 +0 x 7 -5 x 12
-64 = +0 x 5 -4 x 7 -3 x 12
-63 = -3 x 5 +0 x 7 -4 x 12
-62 = +0 x 5 -2 x 7 -4 x 12
-61 = -5 x 5 +0 x 7 -3 x 12
-60 = +0 x 5 +0 x 7 -5 x 12
-59 = +0 x 5 -5 x 7 -2 x 12
-58 = -2 x 5 +0 x 7 -4 x 12
-57 = +0 x 5 -3 x 7 -3 x 12
-56 = -4 x 5 +0 x 7 -3 x 12
-55 = +0 x 5 -1 x 7 -4 x 12
-54 = -6 x 5 +0 x 7 -2 x 12
-53 = -1 x 5 +0 x 7 -4 x 12
-52 = +0 x 5 -4 x 7 -2 x 12
-51 = -3 x 5 +0 x 7 -3 x 12
-50 = +0 x 5 -2 x 7 -3 x 12
-49 = -5 x 5 +0 x 7 -2 x 12
-48 = +0 x 5 +0 x 7 -4 x 12
-47 = +0 x 5 -5 x 7 -1 x 12
-46 = -2 x 5 +0 x 7 -3 x 12
-45 = +0 x 5 -3 x 7 -2 x 12
-44 = -4 x 5 +0 x 7 -2 x 12
-43 = +0 x 5 -1 x 7 -3 x 12
-42 = -6 x 5 +0 x 7 -1 x 12
-41 = -1 x 5 +0 x 7 -3 x 12
-40 = +0 x 5 -4 x 7 -1 x 12
-39 = -3 x 5 +0 x 7 -2 x 12
-38 = +0 x 5 -2 x 7 -2 x 12
-37 = -5 x 5 +0 x 7 -1 x 12
-36 = +0 x 5 +0 x 7 -3 x 12
-35 = +0 x 5 -5 x 7 +0 x 12
-34 = -2 x 5 +0 x 7 -2 x 12
-33 = +0 x 5 -3 x 7 -1 x 12
-32 = -4 x 5 +0 x 7 -1 x 12
-31 = +0 x 5 -1 x 7 -2 x 12
-30 = -6 x 5 +0 x 7 +0 x 12
-29 = -1 x 5 +0 x 7 -2 x 12
-28 = +0 x 5 -4 x 7 +0 x 12
-27 = -3 x 5 +0 x 7 -1 x 12
-26 = +0 x 5 -2 x 7 -1 x 12
-25 = -5 x 5 +0 x 7 +0 x 12
-24 = +0 x 5 +0 x 7 -2 x 12
-23 = +1 x 5 -4 x 7 +0 x 12
-22 = -2 x 5 +0 x 7 -1 x 12
-21 = +0 x 5 -3 x 7 +0 x 12
-20 = -4 x 5 +0 x 7 +0 x 12
-19 = +0 x 5 -1 x 7 -1 x 12
-18 = -5 x 5 +1 x 7 +0 x 12
-17 = -1 x 5 +0 x 7 -1 x 12
-16 = +1 x 5 -3 x 7 +0 x 12
-15 = -3 x 5 +0 x 7 +0 x 12
-14 = +0 x 5 -2 x 7 +0 x 12
-13 = -4 x 5 +1 x 7 +0 x 12
-12 = +0 x 5 +0 x 7 -1 x 12
-11 = +2 x 5 -3 x 7 +0 x 12
-10 = -2 x 5 +0 x 7 +0 x 12
-9 = +1 x 5 -2 x 7 +0 x 12
-8 = -3 x 5 +1 x 7 +0 x 12
-7 = +0 x 5 -1 x 7 +0 x 12
-6 = -4 x 5 +2 x 7 +0 x 12
-5 = -1 x 5 +0 x 7 +0 x 12
-4 = +2 x 5 -2 x 7 +0 x 12
-3 = -2 x 5 +1 x 7 +0 x 12
-2 = +1 x 5 -1 x 7 +0 x 12
-1 = -3 x 5 +2 x 7 +0 x 12
0 = +0 x 5 +0 x 7 +0 x 12
1 = +3 x 5 -2 x 7 +0 x 12
2 = -1 x 5 +1 x 7 +0 x 12
3 = +2 x 5 -1 x 7 +0 x 12
4 = -2 x 5 +2 x 7 +0 x 12
5 = +1 x 5 +0 x 7 +0 x 12
6 = +4 x 5 -2 x 7 +0 x 12
7 = +0 x 5 +1 x 7 +0 x 12
8 = +3 x 5 -1 x 7 +0 x 12
9 = -1 x 5 +2 x 7 +0 x 12
10 = +2 x 5 +0 x 7 +0 x 12
11 = -2 x 5 +3 x 7 +0 x 12
12 = +0 x 5 +0 x 7 +1 x 12
13 = +4 x 5 -1 x 7 +0 x 12
14 = +0 x 5 +2 x 7 +0 x 12
15 = +3 x 5 +0 x 7 +0 x 12
16 = -1 x 5 +3 x 7 +0 x 12
17 = +1 x 5 +0 x 7 +1 x 12
18 = +5 x 5 -1 x 7 +0 x 12
19 = +0 x 5 +1 x 7 +1 x 12
20 = +4 x 5 +0 x 7 +0 x 12
21 = +0 x 5 +3 x 7 +0 x 12
22 = +2 x 5 +0 x 7 +1 x 12
23 = -1 x 5 +4 x 7 +0 x 12
24 = +0 x 5 +0 x 7 +2 x 12
25 = +5 x 5 +0 x 7 +0 x 12
26 = +0 x 5 +2 x 7 +1 x 12
27 = +3 x 5 +0 x 7 +1 x 12
28 = +0 x 5 +4 x 7 +0 x 12
29 = +1 x 5 +0 x 7 +2 x 12
30 = +6 x 5 +0 x 7 +0 x 12
31 = +0 x 5 +1 x 7 +2 x 12
32 = +4 x 5 +0 x 7 +1 x 12
33 = +0 x 5 +3 x 7 +1 x 12
34 = +2 x 5 +0 x 7 +2 x 12
35 = +0 x 5 +5 x 7 +0 x 12
36 = +0 x 5 +0 x 7 +3 x 12
37 = +5 x 5 +0 x 7 +1 x 12
38 = +0 x 5 +2 x 7 +2 x 12
39 = +3 x 5 +0 x 7 +2 x 12
40 = +0 x 5 +4 x 7 +1 x 12
41 = +1 x 5 +0 x 7 +3 x 12
42 = +6 x 5 +0 x 7 +1 x 12
43 = +0 x 5 +1 x 7 +3 x 12
44 = +4 x 5 +0 x 7 +2 x 12
45 = +0 x 5 +3 x 7 +2 x 12
46 = +2 x 5 +0 x 7 +3 x 12
47 = +0 x 5 +5 x 7 +1 x 12
48 = +0 x 5 +0 x 7 +4 x 12
49 = +5 x 5 +0 x 7 +2 x 12
50 = +0 x 5 +2 x 7 +3 x 12
51 = +3 x 5 +0 x 7 +3 x 12
52 = +0 x 5 +4 x 7 +2 x 12
53 = +1 x 5 +0 x 7 +4 x 12
54 = +6 x 5 +0 x 7 +2 x 12
55 = +0 x 5 +1 x 7 +4 x 12
56 = +4 x 5 +0 x 7 +3 x 12
57 = +0 x 5 +3 x 7 +3 x 12
58 = +2 x 5 +0 x 7 +4 x 12
59 = +0 x 5 +5 x 7 +2 x 12
60 = +0 x 5 +0 x 7 +5 x 12
61 = +5 x 5 +0 x 7 +3 x 12
62 = +0 x 5 +2 x 7 +4 x 12
63 = +3 x 5 +0 x 7 +4 x 12
64 = +0 x 5 +4 x 7 +3 x 12
65 = +1 x 5 +0 x 7 +5 x 12
66 = +6 x 5 +0 x 7 +3 x 12
67 = +0 x 5 +1 x 7 +5 x 12
68 = +4 x 5 +0 x 7 +4 x 12
69 = +0 x 5 +3 x 7 +4 x 12
70 = +2 x 5 +0 x 7 +5 x 12
71 = +0 x 5 +5 x 7 +3 x 12
72 = +0 x 5 +0 x 7 +6 x 12
73 = +5 x 5 +0 x 7 +4 x 12
74 = +0 x 5 +2 x 7 +5 x 12
75 = +3 x 5 +0 x 7 +5 x 12
76 = +0 x 5 +4 x 7 +4 x 12
77 = +1 x 5 +0 x 7 +6 x 12
78 = +6 x 5 +0 x 7 +4 x 12
79 = +0 x 5 +1 x 7 +6 x 12
80 = +4 x 5 +0 x 7 +5 x 12
81 = +0 x 5 +3 x 7 +5 x 12
82 = +2 x 5 +0 x 7 +6 x 12
83 = +0 x 5 +5 x 7 +4 x 12
84 = +0 x 5 +0 x 7 +7 x 12
85 = +5 x 5 +0 x 7 +5 x 12
86 = +0 x 5 +2 x 7 +6 x 12
87 = +3 x 5 +0 x 7 +6 x 12
88 = +0 x 5 +4 x 7 +5 x 12
89 = +1 x 5 +0 x 7 +7 x 12
90 = +6 x 5 +0 x 7 +5 x 12
91 = +0 x 5 +1 x 7 +7 x 12
92 = +4 x 5 +0 x 7 +6 x 12
93 = +0 x 5 +3 x 7 +6 x 12
94 = +2 x 5 +0 x 7 +7 x 12
95 = +0 x 5 +5 x 7 +5 x 12
96 = +0 x 5 +0 x 7 +8 x 12
97 = +5 x 5 +0 x 7 +6 x 12
98 = +0 x 5 +2 x 7 +7 x 12
99 = +3 x 5 +0 x 7 +7 x 12
100 = +0 x 5 +4 x 7 +6 x 12

xugucheng 2011-06-26
  • 打赏
  • 举报
 回复
[Quote=引用楼主 sflyingdream 的回复:]
rt
[/Quote]好像10是权2：（5+5）？
加载更多回复（55）
软件课程设计 试验报告 代码 演示
1基础题_2.由计算机生成简单的四则运算题 1.1 需求分析： 本题主要是要求设计一个可以自动生成四则运算的测试器，并且完全由用户决定出加、减、乘、除哪一种运算题，以及出一位数还是两位数的运算题，同时还要对用户给出的答案的对错进行判断。在程序运行过程中，用户可以选择何时结束程序，并在结束程序时给出一个某种形式的成绩。 ///////////////////////////////////////////// 程序执行的结果：/////////////////////////////////////////////////// 1.2 概要设计： 在对题目理解的基础上，并针对几个特别的技术环节，我认为程序可分为三个部分： 1） 程序的欢迎界面，主要通过一些特殊制表符来完成。其中运行，退出程序可以通过一个while循环来判定同时还要考虑用户输入信号量的正误； 2） 出题函数，也是本程序最关键的一个函数，通过使用“rand()%10”或“rand()%100”来获得一个0到9的一位整数随机值或得到0到99的两位整数随机值来为用户出题，并判断用户答案的对错； 3） 评分系统，是在用户选择退出后对用户所答题情况给出的成绩评价。 /////////////////////////////////////////////////// 程序流程图： 1.3 详细设计与编码： 为了使程序更加简洁与工整，且容易修改和阅读，我采用头文件的方式将Exam()函数放在了Exam .h中。Exam()函数主要负责程序的出题和结果的判断，其输入接口为运算符号，位数，即只需向其输入四则运算的一种符号和运算的位数，函数便自动生成题目并自动判断结果的正误，结果以1，0返回。而主程序则是完成了程序的开始、结束，用户成绩的判定。 /////////////////////////////////////////////////// 具体源程序如下： ---------------------------------------------------------------------------------------------------------------------- int Exam(int figure, int sign) {//本函数负责给用户出题 if (figure!=1&&figure!=2&&sign<1&&sign>4) return 0; //判断函数的输入是否符合要求 int a, b; if (figure==1) a=rand()%10; b=rand()%10; if (figure==2) a=rand()%100; b=rand()%100; switch(sign) { case(1): { cout<<" "<>r; if(r!=a+b) { cout<<" "<<"╳ 很遗憾，回答错误! X﹏X "<