前一篇: 后一篇:
点击此处发表评论
验证码：&&
以上网友发言只代表个人观点，请勿理解为数苑网的观点或立场。
Copyright @2000- All Rights Reserved
Sciyard数苑网 版权所有21ic官方微信-->
后使用快捷导航没有帐号？
查看: 3663|回复: 12
矩阵键盘的问题
&&已结帖(5)
主题帖子积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
主题帖子积分
专家等级：结帖率：100%
主题帖子积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
我有一次面试，问我矩阵键盘同时按下多个键会出现什么情况。
比如2个键，3个键或4个键。
我吃不准，是会误判还是烧坏键盘？
请高手指教，谢谢！
满意回复+4
应该是两个或以上的相连的IO都同时设为输出了,而且有些输出1,有些输出0,时间长了就会损坏IO
典型的程序问题
一般可以通过串电阻来处理,但程序本身的BUG还是 ...
硬件不会怎么样啊，主要看程序怎么写啊，像我一般写的就是扫描到第一个按下的键，其他的会被忽略掉啊。当然如果程序设计成组合键的，就不会了。 ...
主题帖子积分
资深技术员, 积分 333, 距离下一级还需 167 积分
资深技术员, 积分 333, 距离下一级还需 167 积分
主题帖子积分
专家等级：结帖率：100%
主题帖子积分
资深技术员, 积分 333, 距离下一级还需 167 积分
资深技术员, 积分 333, 距离下一级还需 167 积分
vvvvvvvvvvvvvvvvvbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvbvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbvvvvvvvvvvvvvvvvvvvvffffffffffffffffffffffffffffffffffffffffffffffgvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvbvgfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffdddddvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvf
主题帖子积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
主题帖子积分
专家等级：结帖率：100%
主题帖子积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
楼上什么意思？
主题帖子积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
主题帖子积分
专家等级：结帖率：100%
主题帖子积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
高手支招啊！
主题帖子积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
主题帖子积分
专家等级：结帖率：100%
主题帖子积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
在网上看到矩阵键盘，简单的不加隔离二极管，多个键按下时通常表现为丢键，有烧IO的隐患（输出为推挽时）。
是这样的吗？高手给讲讲。
主题帖子积分
技术总监, 积分 39802, 距离下一级还需 10198 积分
技术总监, 积分 39802, 距离下一级还需 10198 积分
主题帖子积分
专家等级：结帖率：3%
主题帖子积分
技术总监, 积分 39802, 距离下一级还需 10198 积分
技术总监, 积分 39802, 距离下一级还需 10198 积分
一般情况是有可能串键(标准的单扫描方式)
但也和程序算法有关,串键其实也可以消除的
主题帖子积分
资深技术员, 积分 387, 距离下一级还需 113 积分
资深技术员, 积分 387, 距离下一级还需 113 积分
主题帖子积分
专家等级：结帖率：100%
主题帖子积分
资深技术员, 积分 387, 距离下一级还需 113 积分
资深技术员, 积分 387, 距离下一级还需 113 积分
主题帖子积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
主题帖子积分
专家等级：结帖率：100%
主题帖子积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
高级工程师, 积分 7792, 距离下一级还需 208 积分
谢谢6楼！烧IO的隐患是怎么回事？请高手指教！
主题帖子积分
技术总监, 积分 39802, 距离下一级还需 10198 积分
技术总监, 积分 39802, 距离下一级还需 10198 积分
主题帖子积分
专家等级：结帖率：3%
主题帖子积分
技术总监, 积分 39802, 距离下一级还需 10198 积分
技术总监, 积分 39802, 距离下一级还需 10198 积分
应该是两个或以上的相连的IO都同时设为输出了,而且有些输出1,有些输出0,时间长了就会损坏IO
典型的程序问题
一般可以通过串电阻来处理,但程序本身的BUG还是要改的
主题帖子积分
助理工程师, 积分 1042, 距离下一级还需 958 积分
助理工程师, 积分 1042, 距离下一级还需 958 积分
主题帖子积分
专家等级：结帖率：58%
主题帖子积分
助理工程师, 积分 1042, 距离下一级还需 958 积分
助理工程师, 积分 1042, 距离下一级还需 958 积分
硬件不会怎么样啊，主要看程序怎么写啊，像我一般写的就是扫描到第一个按下的键，其他的会被忽略掉啊。当然如果程序设计成组合键的，就不会了。
主题帖子积分
实习生, 积分 6, 距离下一级还需 44 积分
实习生, 积分 6, 距离下一级还需 44 积分
主题帖子积分
专家等级：结帖率：0%
主题帖子积分
实习生, 积分 6, 距离下一级还需 44 积分
实习生, 积分 6, 距离下一级还需 44 积分
ghost key--&对于矩阵扫描原理的键盘，支持多按键输入系统时一定会要求能有效判断出串键，如下图（本来想发图，不知道始何发）：当按下key1,再按下key2,然后当第三个键盘出现在key4 或key3位置时，你始何区分只是按下其中的某一个，而不是全部,
& && && && && && && &&&row1& && && &&&row2
& && && && && && && && &|& && && && && && & |
col1& && & ------ key1---------ghostkey4------& &
& && && && && && && && &|& && && && && && & |
col2& && & ------ghostkey3---&&key 2---------
& && && && && && && && &|& && && && && && & |
主题帖子积分
初级技术员, 积分 81, 距离下一级还需 19 积分
初级技术员, 积分 81, 距离下一级还需 19 积分
主题帖子积分
专家等级：结帖率：0%
主题帖子积分
初级技术员, 积分 81, 距离下一级还需 19 积分
初级技术员, 积分 81, 距离下一级还需 19 积分
我觉得就看现实中的计算器,你同时按下去几个按键看看有什么结果,当然也与你写的程序控制方式有关,我想他也只是想让你回答出几种可能的情况.
不学无以成才.
希望单片机(用C的同志).PRO.E结构设计.PCB设计.LED设计(包括室内照明)的同志们加我Q:, 一起交流.加油!
主题帖子积分
主题帖子积分
专家等级：结帖率：0%
主题帖子积分
无冕之王奖章
等级类勋章
奔腾之江水
发帖类勋章
时间类勋章
技术奇才奖章
人才类勋章
涓涓之细流
发帖类勋章
时间类勋章
荣誉元老奖章
等级类勋章
坚毅之洋流
发帖类勋章
时间类勋章
技术领袖奖章
人才类勋章
技术高手奖章
人才类勋章
时间类勋章
社区建设奖章
等级类勋章
欢快之小溪
发帖类勋章
热门推荐 /2矩阵连乘详解
&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&--crystal
AmnBnpAB(AB)mp
M1,M2,M3,M41020,
11004ApqBqrABABprABqq-1ABpqr
M1(M2(M3M4))
(M1(M2M3))M4
M3M450*1*100=5,000M2(M3M4)20*50*100=100,000
M1(M2(M3M4))10*20*100=20,000
(M2M3)20*50*1=1000(M1(M2M3))10*20*1=200
(M1(M2M3))M410*1*100=1000
MiMi+1Mj-1Mji&jj-i+1j-i+1
j-i(j-i)Mi(Mi+1Mj)(MiMi+1)(Mi+2Mj)(MiMi+1Mj-1)Mjj-ij-iMj-1Mji&jj-i(Mk)
(Mk+1Mj)ik&j
tMtrtrt-1MtMiMkri-1rk
Mk+1Mjrkrjri-1rkrj
j-i(MiMk)(Mj)mi,kmk+1,j(MiMk)(Mk+1Mj)
mi,k &&+&&
ik&j j-iMiMi+1Mj-1Mji&jmi,j
(k=1,i&=k&j)
m1,2=min{ m1,1& +& m2,2& +&
ri-1riri+1
=ri-1riri+1=r0r1r2=
102050=10000m23i=2,
j=3ri-1riri+1=r1r2r3=20501=1000
j=3minik&j{mik+mk+1,j+rkrj}=
min{ (m11+m23+r0r1r3)(k=1)(m12+m33+r0r2r3)(k=2)}=
min{(0+), ()}= min{}=1200
A[i][j]&&&&
mi,jm[i][j]Mj-1Mji&j
MiMkMk+1Mjri-1rkrj =
ri-1rkrj& kmi,jmi,jok&
ri-1rkrj&&
mk+1,j mi,j
int min(int a,intb){
return a&b?a:b;
int int i,int j){
int i,j,k,t,u;
if(i==j)&&
return 0;&
//i==j时就是mi,i，也就是单个矩阵，当然，单个矩阵不存在乘积所以为0
if(i==j-1)&&
return p[i-1]*p[i]*p[j];&&
//明显，这是相邻的两个矩阵的乘积
u=d(i,i)+d(i+1,j)+p[i-1]*p[i]*p[j];&&
for(k=i+1;k&j;k++){&&&&&&&&&&&&&&&&&&
u=min(t,u);&&&&&&&&&&&&&&&&&&&&&
ijk==imi,j
就是rkrj&&
O(2^n)timelimitexceededmemorylimitexceededdp()dp
int dp_matrix_multiply(){
int i,j,r,k,
for(i=1;i&=n;i++)&&&
m[i][i]=0;&&&&&
for(r=2;r&=n;r++){&&&
for(i=1;i&=n-r+1;i++){& //3
&&&&&&&&&&&
j=i+r-1;&&&&&&&&&&
&&&&&&&&&&&
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];&&
&&&&&&&&&&&
for(k=i+1;k&j;k++){&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&
m[i][j]=tem&m[i][j]?tem:m[i][j];&&&&&&&&&&&
&&&&&&&&&&&
return m[1][n];
the matrix train length2(1)r==1r==2r& mi,j=min {&&
ri-1rkrj&&
mi,j& mi,k& & mk+1,jmi,kmk+1,jmi,idp423dpt=+d(k+1,j)+p[i-1]*p[k]*p[j];改成了tem=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];这样用数组记录状态节约了大量的时间，因为递归方法中d(i,k)这个函数总是被多次调用，不能用递归的方法解决大数据的原因就在于此。
理解了上面的内容注释3的意思也不难看懂了，i和j就是MiMi+1Mj-1Mji&jiji1n-r+1ji+r-1i1n-r+1r(1),jr
&&&&&&&&&&&&&&
#include &stdio.h&
#include &string.h&
#include &stdlib.h&
#define len 105
int m[len][len],p[len];
bool input(){
if(scanf("%d",&n)==1&&n&0){
for(i=0;i&n;i++)
&&&&&&&&&&&
scanf("%d",&p[i]);
return true;
else return 0;
int dp_matrix_multiply(){
int i,j,r,k,
for(i=1;i&=n;i++)
m[i][i]=0;
for(r=2;r&=n;r++){
for(i=1;i&=n-r+1;i++){
&&&&&&&&&&&
&&&&&&&&&&&
&&&&&&&&&&&
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
&&&&&&&&&&&
for(k=i+1;k&j;k++){
&&&&&&&&&&&&&&&
tem=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
&&&&&&&&&&&&&&&
m[i][j]=tem&m[i][j]?tem:m[i][j];
&&&&&&&&&&&
return m[1][n];
int main(void){
while(input()){
ans=dp_matrix_multiply();
printf("%d\n",ans);
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。算法题：矩阵链乘问题
算法题：矩阵链乘问题
矩阵链乘问题是最典型的动态规划问题，要理解下面的内容请先阅读这篇动态规划的总结。
1.问题描述
矩阵链乘问题的描述如下，就是说要确定一个完全加括号的形式使得矩阵链乘需要进行的标量计算数目最少，矩阵Ai的维数为pi-1×pi，如果穷举所有可能形式的话，时间复杂度是指数级的！因为该问题满足最优子结构，并且子问题存在重叠，所以我们可以借助动态规划来求解。
2.问题分析
我们需要确定一个递归式来将我们要求解的问题表示出来，下面摘自导论，介绍地非常详细
最后给出的递归式如下，就是说我们要如何确定从第i个矩阵到第j个矩阵组成的矩阵链的最优解。如果i和j相等，那么就是一个矩阵，不需要运算；如果i小于j，那么肯定要从它们中间的某个位置分开来，那从哪里分开来呢? 这个我们可以尝试下所有可能的选择，也就是尝试不同的位置k，k满足条件(i <=k < j)，在位置k将矩阵链进行分开，看看它需要的计算次数，然后我们从这些可能的k中选择使得计算次数最小的那个k进行分开，分开了之后我们的问题就变成了2个小问题，确定矩阵链从i到k 和另一个矩阵链从k+1到j的最优解。如果我们一开始设置i=1(第一个矩阵)，j=n(最后一个矩阵)，那么，经过上面的递归即可得到我们需要的解。这就是递归的思想！
3.代码实现
根据上面的思想我们很快就可以写出一个递归版本的矩阵链承法的实现代码，输出的结果也没有错，给出的加括号的方式是( ( A1 ( A2 A3 ) ) ( ( A4 A5 ) A6 ) )。[问题的数据是导论中的问题的数据，值是30,35,15,5,10,20,25]。
def matrixchain_rec(p,i,j):
k in range(i,j):
q=matrixchain_rec(p,i,k)+matrixchain_rec(p,k+1,j)+p[i-1]*p[k]*p[j]
if q<m[i][j]:
return m[i][j]
def showmatrixchain(s,i,j):
print A%d%(i),
print (,
showmatrixchain(s,i,s[i][j])
showmatrixchain(s,s[i][j]+1,j)
print ),
p=[30,35,15,5,10,20,25]
m=[[sys.maxint for i in range(n+1)] for j in range(n+1)]
s=[[0 for i in range(n+1)] for j in range(n+1)]
# pprint.pprint(m)
result=matrixchain_rec(p,1,6)
print(result) #15125
showmatrixchain(s,1,6) #( ( A1 ( A2 A3 ) ) ( ( A4 A5 ) A6 ) )
上面的代码运行没有问题，但是，它不够完美！为什么呢? 很明显，矩阵链乘问题子问题存在重叠，下面这张图很形象地显示了哪些子问题被重复计算了，所以我们需要改进，改进的方法就是使用带备忘录的递归形式！
要改成带备忘录的很简单，但是，这次我们不能直接使用原来的装饰器，因为Python中的dict不能对list对象进行hash，所以我们要简单地修改下我们key值的构建，也很简单，看下代码就明白了：
from ctools import wraps
def memo(c):
def wrap(*args):
#build new key!!!
key=str(args[1])+str(args[2])
if key not in cache:
cache[key]=c(*args)
return cache[key]
return wrap
def matrixchain_rec(p,i,j):
k in range(i,j):
q=matrixchain_rec(p,i,k)+matrixchain_rec(p,k+1,j)+p[i-1]*p[k]*p[j]
if q<m[i][j]:
return m[i][j]
def showmatrixchain(s,i,j):
print A%d%(i),
print (,
showmatrixchain(s,i,s[i][j])
showmatrixchain(s,s[i][j]+1,j)
print ),
p=[30,35,15,5,10,20,25]
m=[[sys.maxint for i in range(n+1)] for j in range(n+1)]
s=[[0 for i in range(n+1)] for j in range(n+1)]
# pprint.pprint(m)
result=matrixchain_rec(p,1,6)
print(result) #15125
showmatrixchain(s,1,6) #( ( A1 ( A2 A3 ) ) ( ( A4 A5 ) A6 ) )
接下来的一个问题是，我们怎么实现迭代版本呢? 迭代版本关键在于顺序！我们怎么保证我们在计算$A{i…j}的最优解时，所有可能的k的选择需要求解的子问题A{i…k}以及A_{(k+1)…j}$是已经求解出来了的呢? 一个简单但是有效的想法就是看矩阵链的长度，我们先计算矩阵链短的最优解，然后再计算矩阵链长的最优解，后者计算时所需要求解的子问题肯定已经求解完了，对不对? 于是就有了迭代版本的实现，需要注意的就是其中的i,j,k的取值范围。
import sys
def matrixchain_iter(p):
n=len(p)-1 #total n matri 6
problem below, so initialize to n+1!!!
i in range(n+1)]
j in range(n+1)]
i in range(n+1)]
j in range(n+1)]
i in range(n): # matrix with len=1
# m[i][i]=0
# pprint.pprint(m)
l in range(2,n+1): #iterate
length, max is n
i in range(1,n-l+2): #i max is n-l+1
j=i+l-1 #j is always l away from i
m[i][j]=sys.maxint #initial to infinity
k in range(i,j):
#attention to
array when index < 0!!!
#solution is using more space with useless values
q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]
if q<m[i][j]:
# print(when len is %d  % (l))
# pprint.pprint(m)
return m,s
m,s=matrixchain_iter(p)
print(m[1][6]) #15125
showmatrixchain(s,1,6) #( ( A1 ( A2 A3 ) ) ( ( A4 A5 ) A6 ) )
实现的时候需要注意一点，在Python中取list中的值时，如果索引是负值的话会从后面往前数返回对应的元素，而以前我们用语言的时候肯定是提示越界了，所以代码中用来存储结果的数数组是(n+1)x(n+1)，而不是nxn的，这样的话就能够保证返回的是0，而不是从后往前数得到的结果。
得到的数组m如下，m[1,6]就是我们需要的解。
[[0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, , 15125],
[0, 0, 0, , ],
[0, 0, 0, 0, 750, ],
[0, 0, 0, 0, 0, ],
[0, 0, 0, 0, 0, 0, 5000],
[0, 0, 0, 0, 0, 0, 0]]
数组s如下：
[[0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 3, 3, 3],
[0, 0, 0, 2, 3, 3, 3],
[0, 0, 0, 0, 3, 3, 3],
[0, 0, 0, 0, 0, 4, 5],
[0, 0, 0, 0, 0, 0, 5],
[0, 0, 0, 0, 0, 0, 0]]
将这个两个数组旋转下，并且只看上三角部分的数字，就可以得到导论中给出的那张三角图形了，非常类似杨辉三角
(有话说)我的个性宣言
　　一个小兵喝得酩酊大醉地回营。&你何必醉成这模样，&长官告诫他道，&你如果不喝酒，可能已经升到上等兵，说不定已经当军官了。&　　&报告上尉，&小兵回答，&我只要一杯酒下肚，就觉得自己是上校了！&
您好，请登录后进行评论。点击
在这里输入评论
五色云平台
关于五色云