本文目录
- Python之动态规划算法
- 怎么用JAVA编程实现实时动态运行的模拟时钟
- 动态规划问题：用c++实现将一个整数分解成若干个整数的和，且这些整数都是2的k次方(k>=0)
- 动态规划求背包问题伪代码讲解
- 求用动态规划的方法求解简单的整数规划问题的matlab程序或者C++程序代码，高手们帮帮忙
- 求Python代码编动态规划贝尔曼函数
- 用汇编语言编写程序，动态显示时间
Python之动态规划算法
动态规划算法中是将复杂问题递归分解为子问题，通过解决这些子问题来解决复杂问题。与递归算法相比，动态编程减少了堆栈的使用，避免了重复的计算，效率得到显著提升。
先来看一个简单的例子，斐波那契数列.
斐波那契数列的定义如下。
斐波那契数列可以很容易地用递归算法实现：
上述代码，随着n的增加，计算量呈指数级增长，算法的时间复杂度是 。
采用动态规划算法，通过自下而上的计算数列的值，可以使算法复杂度减小到 ，代码如下。
下面我们再看一个复杂一些的例子。
这是小学奥数常见的硬币问题： 已知有1分，2分，5分三种硬币数量不限，用这些硬币凑成为n分钱，那么一共有多少种组合方法。
我们将硬币的种类用列表 coins 定义； 将问题定义为一个二维数组 dp，dp )凑成总价amt的组合数。
例如： coins =
dp 凑成总和为5的组合数。
对于所有的 dp 为1。
对于 dp 硬币总价amt的组合数，包含两种情况计算：
1.当使用第j个硬币时，有 dp 种情况，即amt减去第j个硬币币值，使用前j+1种硬币的组合数；
2.当不使用第j个硬币时，有 dp 种情况，即使用前j种硬币凑成amt的组合数；
所以： dp
我们最终得到的结果是：dp
上述分析省略了一些边界情况。
有了上述的分析，代码实现就比较简单了。
动态规划算法代码简洁，执行效率高。但是与递归算法相比，需要仔细考虑如何分解问题，动态规划代码与递归调用相比，较难理解。
我把递归算法实现的代码也附在下面。有兴趣的朋友可以比较一下两种算法的时间复杂度有多大差别。
上述代码在Python 3.7运行通过。
怎么用JAVA编程实现实时动态运行的模拟时钟
import java.awt.*;import java.applet.Applet;import java.util.Calendar;import java.text.SimpleDateFormat;import java.util.Date;public class ClockApplet extends Applet implements Runnable //Applet支持线程{ private Thread athread; //线程 private SimpleDateFormat sdateformat; //日期格式public void init() { this.setBackground(Color.white);//背景颜色设为白色 this.athread = null; } public void paint(Graphics g) { this.sdateformat = new SimpleDateFormat("hh时mm分ss秒"); g.drawString(this.sdateformat.format(new Date()),25,131); Calendar rightnow = Calendar.getInstance(); int second = rightnow.get(Calendar.SECOND); int minute = rightnow.get(Calendar.MINUTE); int hour = rightnow.get(Calendar.HOUR); //半径 int R_H = 20,R_M = 4,R_S = 4; //时针的坐标 //x ====(9-3) //y ====(12-6) int H_x ; int H_y; //x if(hour == 0) { hour = 12; } if( hour 》= 3 && hour 《= 9 ) { H_x = R_H*Math.abs(hour - 9); } else { if(hour 》 9) { H_x = R_H*Math.abs(hour - 9); } else { H_x = R_H*Math.abs(hour+3); } } //y if( hour 》= 6 && hour 《= 12 ) { H_y = R_H*Math.abs(hour - 12); } else { H_y = R_H*hour; } //分针的坐标 int M_x; int M_y; if(minute == 0) { minute = 60; } if( minute 》= 15 && minute 《= 45 ) { M_x = R_M*Math.abs(minute - 45); } else { if(minute 》 45) { M_x = R_M*Math.abs(minute - 45); } else { M_x = R_M*Math.abs(minute+15); } } //y if( minute 》= 30 && minute 《 60 ) { M_y = R_M*Math.abs(minute - 60); } else { M_y = R_M*minute; } //秒针的坐标 int S_x; int S_y; if(second == 0) { second = 60; } if( second 》= 15 && second 《= 45 ) { S_x = R_S*Math.abs(second - 45); } else { if(second 》 45) { S_x = R_S*Math.abs(second - 45); } else { S_x = R_S*Math.abs(second+15); } } //y if( second 》= 30 && second 《= 60 ) { S_y = R_S*Math.abs(second - 60); } else { S_y = R_S*second; }// g.drawString(String.valueOf(second),25,50);// g.drawString(String.valueOf(minute),25,60); // g.drawString(String.valueOf(hour),25,70); // g.drawString(String.valueOf(H_x),25,80); // g.drawString(String.valueOf(H_y),25,90); g.drawOval(0,0,120,120);//距离相差10像素 g.setColor(Color.darkGray); g.drawString("9",5,65); g.drawString("3",110,65); g.drawString("12",55,15); g.drawString("6",55,115); g.drawString("1",80,20); g.drawString("2",100,40); g.drawString("4",100,90); g.drawString("5",80,110); g.drawString("7",30,110); g.drawString("8",10,90); g.drawString("10",10,40); g.drawString("11",30,20); g.setColor(Color.red); g.drawLine(60,60,H_x,H_y);//前一个点表示起点，另一个表示终点 g.setColor(Color.blue); g.drawLine(60,60,M_x,M_y); g.setColor(Color.yellow); g.drawLine(60,60,S_x,S_y);} public void start() { if(athread == null) { athread = new Thread(this); athread.start(); } } public void stop() { if(athread != null) { athread.interrupt(); athread = null; } } public void run() { while(athread != null) { repaint(); try { athread.sleep(1000); } catch(InterruptedException e) { } } }}
动态规划问题：用c++实现将一个整数分解成若干个整数的和，且这些整数都是2的k次方(k>=0)
动态规划转移方程：a ,n是奇数a ,n 是偶数代码：#include《iostream》using namespace std;__int64 a;int flag(0);int main(){ a = 1; a = 1; a = 2; while(cin》》n,n) //input integer n { for(int i=flag;i《=n;++i) { if(i&1) a%1000000000; else a)%1000000000; } flag = n; cout《《a《《endl; } return 0;}方程的想法有一点难以理解，其实你仔细想想也是可以理解的，需要细细琢磨
动态规划求背包问题伪代码讲解
开一个bool数组f，f表示是否可以用前i件物品【刚好】占用j的容量，初始化f=true。然后：for i=1 to n for j=w to s f;最后输出结果只需看f是否为true，为true则存在可行解，否则不存在。输出解集的方法就是再开一个数组g，g记录当前位是选择了物品i还是没有选择物品i，这样完整的代码如下：//DPfor i=1 to n for j=w to s if f==true f=false; else if f==true f=true;//outputj=s;i=n;while i》=1 { if g==true 输出物品i,j=j-w,i=i-1; else 不用输出物品i,i=i-1;}不知道您能不能看懂，输出解集部分跟普通的01背包是一样的，建议您参考《背包九讲》，如果觉得我写的不清楚欢迎提问。希望能帮到您。
求用动态规划的方法求解简单的整数规划问题的matlab程序或者C++程序代码，高手们帮帮忙
max Z=4x1+5x2 +6x3s.t. 3x1+4x2+5x3《=10 x1,x2,x3》=0且都为整数约束条件分析：x1=1,2,3x2=1,2x3=1,2阶段变量：x1、x2、x3状态变量：决策变量：目标函数：Z=4x1+5x2 +6x3状态转移方程：约束条件用惩罚处理……未完待续……
求Python代码编动态规划贝尔曼函数
class Node(object): def __init__(self, name): self._name = name self._value = None self._from = None self._next = def setValue(self, value): self._value = value def setNext(self, node): self._next.append(node) def setFrom(self, node): self._from = node def getValue(self): return self._value def getNext(self): return self._next def getName(self): return self._name def getFrom(self): return self._from class BFtree(): def __init__(self, dList): self._dList = dList def bfValue(self, start): cur = start if cur.getNext() is not None: for node in cur.getNext(): path = path.sort() path = ’’.join(path) value = cur.getValue() + self._dList if node.getValue() is None or value 《 node.getValue(): node.setValue(value) node.setFrom(cur) self.bfValue(node) def move(self, start, end): print ’From: ’, start.getName(), ’ to: ’, end.getName() start.setValue(0) self.bfValue(start) trace = cur = end while cur.getFrom() is not None: cur = cur.getFrom() trace.append(cur.getName()) trace = reversed(trace) print ’The path is ’, ’ ’.join(trace),’ and the value is ’, end.getValue() #builidng nodea = Node(’A’)b = Node(’B’)c = Node(’C’)d = Node(’D’)e = Node(’E’)f = Node(’F’)g = Node(’G’)h = Node(’H’)#build treea.setNext(b)a.setNext(c)a.setNext(d)b.setNext(a)b.setNext(g)c.setNext(a)c.setNext(g)c.setNext(e)d.setNext(a)d.setNext(e)e.setNext(c)e.setNext(b)e.setNext(f)f.setNext(e)g.setNext(b)g.setNext(c)g.setNext(h)h.setNext(g)#build distance listdList = dict();dList = 1dList = 2dList = 3dList = 1dList = 6dList = 2dList = 5dList = 4dList = 3dList = 4#build BFtreetree = BFtree(dList)tree.move(a,h)tree.move(a,f)tree.move(a,e)
代码略长....
用汇编语言编写程序，动态显示时间
cursor equ 45H attrib equ 2fh code segment assume cs:code,ds:code start: jmp go oldcur dw ? OLD1C DW 2 DUP(?) NEWINT1C: PUSHF CALL DWORD PTR CS:OLD1C push ax PUSH BX PUSH CX PUSH DX XOR BH,BH MOV AH,3 INT 10H MOV CS:OLDCUR,DX MOV AH,2 xor bh,bh MOV DX,CURSOR INT 10H MOV AH,2; ；读取系统时钟 INT 1AH PUSH DX PUSH CX POP BX PUSH BX CALL SHOWBYTE CALL SHOWCOLON POP BX XCHG BH,BL CALL SHOWBYTE CALL SHOWCOLON POP BX CALL SHOWBYTE MOV DX,CS:OLDCUR MOV AH,2 XOR BH,BH INT 10H POP DX POP CX POP BX POP AX IRET SHOWBYTE PROC NEAR PUSH BX MOV CL,4 MOV AL,BH SHR AL,CL ADD AL,30H CALL SHOW CALL CURMOVE POP BX MOV AL,BH AND AL,0FH ADD AL,30H CALL SHOW CALL CURMOVE RET SHOWBYTE ENDPSHOWCOLON PROC NEAR MOV AL,’:’ CALL SHOW CALL CURMOVE RET SHOWCOLON ENDPCURMOVE PROC NEAR PUSH AX PUSH BX PUSH CX PUSH DX MOV AH,3 MOV BH,0 INT 10H INC DL MOV AH,2 INT 10H POP DX POP CX POP BX POP AX RET CURMOVE ENDPSHOW PROC NEAR PUSH AX PUSH BX PUSH CX MOV AH,09H MOV BX,attrib MOV CX,1 INT 10H POP CX POP BX POP AX RET SHOW ENDPGO: PUSH CS POP DS MOV AX,351CH ;取中断向量 INT 21H MOV OLD1C,BX; ；保存原中断向量 MOV BX,ES MOV OLD1C+2,BX MOV DX,OFFSET NEWINT1C; ；置新的中断向量 MOV AX,251CH INT 21H MOV DX,OFFSET GO SUB DX,OFFSET START MOV CL,4 SHR DX,CL ADD DX,11H MOV AX,3100H; ；结束并驻留 INT 21H CODE ENDS END START-----------------------------------------------------------------------------------cursor equ 45H ;定义显示位置 attrib equ 2fh ;定义时钟显示颜色，绿底白字 code segment assume cs:code,ds:code start: jmp go ;转到程序预处理，设置中断并驻留 oldcur dw ? ;用于保存原来光标位置 OLD1C DW 2 DUP(?) ;用于保存原来的 int 1c 入口地址 NEWINT1C: ;新的 int 1c 入口 PUSHF ;标志压栈 CALL DWORD PTR CS:OLD1C ;调用原来的 int 1c 中断 push ax PUSH BX PUSH CX PUSH DX XOR BH,BH MOV AH,3 INT 10H ;int10 子功能 03 取当前光标位置 MOV CS:OLDCUR,DX ;当前光标位置存入CS:OLDCUR MOV AH,2 xor bh,bh MOV DX,CURSOR ;DX=CURSOR=45h，表示光标定位在1 行70 列 INT 10H ;int10 子功能 02 设置光标位置 MOV AH,2 INT 1AH ;INT 1AH 子功能 02 读取系统时钟，返回CH/CL/DH=BCD码小时/BCD码分钟/BCD码秒 PUSH DX PUSH CX POP BX ;小时分钟数给BX PUSH BX CALL SHOWBYTE ;调用子程序显示小时，小时在bh中 CALL SHOWCOLON ;调用子程序显示时间分隔符 ":" POP BX XCHG BH,BL ;分钟给bh CALL SHOWBYTE ;调用子程序显示分钟，bh是分钟数 CALL SHOWCOLON ;调用子程序显示时间分隔符 ":" POP BX ;秒数给bh CALL SHOWBYTE ;调用子程序显示秒数 MOV DX,CS:OLDCUR ;读取备份的光标位置 MOV AH,2 XOR BH,BH INT 10H ;int10 子功能 02 还原原来的光标位置 POP DX POP CX POP BX POP AX IRET ;中断返回SHOWBYTE PROC NEAR ;BCD值显示子程序，BCD值在BH中 PUSH BX ;压栈BX值，以防冲掉 MOV CL,4 ;以下代码BH中BCD十位值转ASCLL码 MOV AL,BH SHR AL,CL ADD AL,30H CALL SHOW ;调用子程序显示AL，当前AL为时间值十位上的数值 CALL CURMOVE ;调用子程序后移光标 POP BX ;还原BX值 MOV AL,BH ;以下代码BH中BCD个位值转ASCLL码 AND AL,0FH ADD AL,30H CALL SHOW ;调用子程序显示AL，当前AL为时间值个位上的数值 CALL CURMOVE ;调用子程序后移光标 RET SHOWBYTE ENDPSHOWCOLON PROC NEAR ;显示字符 ":" 子程序，用于时间分隔符 MOV AL,’:’ CALL SHOW ;调用子程序显示":" CALL CURMOVE ;调用子程序后移光标 RET SHOWCOLON ENDPCURMOVE PROC NEAR ;光标后移子程序 PUSH AX PUSH BX PUSH CX PUSH DX MOV AH,3 MOV BH,0 INT 10H ;取光标位置 INC DL ;光标列位置加1 MOV AH,2 INT 10H ;设光标位置 POP DX POP CX POP BX POP AX RET CURMOVE ENDPSHOW PROC NEAR ;显示一个ASCLL字符子程序，AL为所显字符 PUSH AX PUSH BX PUSH CX MOV AH,09H MOV BX,attrib ;BH/BL=字符背景色/字符颜色 ，attrib=2fh=绿底白字 MOV CX,1 ;显示个数 1 INT 10H ;int 10 子功能 09 显示一个字符 POP CX POP BX POP AX RET SHOW ENDPGO: PUSH CS POP DS MOV AX,351CH ;取时钟中断 int 1c中断原入口 INT 21H MOV OLD1C,BX ;保存原中断向量 MOV BX,ES MOV OLD1C+2,BX MOV DX,OFFSET NEWINT1C ;设置新的时钟中断 int 1c 入口 MOV AX,251CH INT 21H MOV DX,OFFSET GO SUB DX,OFFSET START ;计算驻留内存字节数 MOV CL,4 SHR DX,CL ;驻留内存值转换为节 ADD DX,11H ;内存数加psp 11节 MOV AX,3100H ;结束并驻留 INT 21H CODE ENDS END STAR
