打印

一个算法问题,请版主帮忙

[复制链接]
3746|22
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
流行音乐|  楼主 | 2010-4-11 18:05 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
问题如下:
如何用软件判断矩阵键盘中是否存在“位于任意某个矩形的四个角上的按键至少有三个按键被按下”。
下面举几个“是”的例子:
1:
x x x x o x
x x x x x x
x o x x o x
x x x x x x
2:
x x x x x x
x x o x x x
x o o x x x
x x x o x x
3:
x x x x x x
x o x o x x
x o x x x x
x x x x o x

下面举几个“否”的例子:
4:
x x x x x x
x x x x x x
x o o o o x
x x x x x x
5:
x x x x x x
x x o o x x
x o x x o x
x x x x x x
6:
x x x x o x
x x x o x x
x o o x x x
x x x x x x

这个问题我考虑了好久还是没有找到头绪,希望帮忙说明一下思路或算法,或给个提示,万分感谢。

相关帖子

沙发
NE5532| | 2010-4-11 18:13 | 只看该作者
在键值上做**,把键盘的键值设计成一个二维数组,比如第一行设计为00 01 02 03,第二行设计为10 11 12 13,以此类推,第一个字节是行坐标,第二个字节是列坐标,然后键盘扫描程序要支持多键同时按下,扫进来以后先判断是不是3个键,是的话用XY坐标对比就知道是不是三角形了。

使用特权

评论回复
板凳
流行音乐|  楼主 | 2010-4-11 18:28 | 只看该作者
有可能有大于3个键同时按下,例如同时按下n个键(n>1),现在想判断这同时按下的n个键中存不存在某3个键位于矩形的4个角上。

使用特权

评论回复
地板
NE5532| | 2010-4-11 19:40 | 只看该作者
最简单的办法是编码,然后遍历

使用特权

评论回复
5
ejack| | 2010-4-11 19:47 | 只看该作者
如果是n个键参与判定,只有遍历了。
当然局部还是有优化的空间的。

使用特权

评论回复
6
流行音乐|  楼主 | 2010-4-11 20:25 | 只看该作者
本帖最后由 流行音乐 于 2010-4-11 20:27 编辑

遍历是指从n个键中每次取3个键进行判断吗?我计算了一下,共有 n!/((n-3)!*3!) 种组合需要判断,软件设计好像有难度。

使用特权

评论回复
7
流行音乐|  楼主 | 2010-4-11 20:40 | 只看该作者
如果我设计一个 n!/((n-3)!*3!) 次的循环,每次循环从n个键中取3个键,如何取才能不会重复,且不会漏取?

使用特权

评论回复
8
NE5532| | 2010-4-11 20:50 | 只看该作者
可以考虑排序

使用特权

评论回复
9
xwj| | 2010-4-11 21:01 | 只看该作者
典型的“丁字键”问题,最主要的问题是对角两键按下时,此时无法判断角上那个按键的按下与释放。

只能从硬件上解决:
要么学习PC键盘,按键错乱排列,让人们的习惯使用时不会有丁字键的出现;
要么每个按键串个二极管,就不怕多键同时按下了。


PS:
一般的操作界面都只处理单按键事件的,最多再处理个双键同按的,而多键同按是应该全都作为无效键值不处理。

使用特权

评论回复
10
流行音乐|  楼主 | 2010-4-11 21:01 | 只看该作者
非常感谢NE5532版主的帮助。
排序是对每次取得的3个键进行排序吗?

使用特权

评论回复
11
328500920| | 2010-4-12 08:41 | 只看该作者
长长见识!呵呵

使用特权

评论回复
12
lenmon650| | 2010-4-12 08:50 | 只看该作者
我不知道你的硬件结构是怎样的~~~不过原理大概都是读IO寄存器吧~~~这样的话只要每次扫描按键的时候判断寄存器里面的数值就好了~~~~还有就是下位机的编程是离不开硬件的~~~不同的硬件组成就有不同的算法~~~~哎~~说太多了~~~~高手就5视我吧

使用特权

评论回复
13
handle09| | 2010-4-12 09:31 | 只看该作者
来混点水 呵呵 楼主按你的方法 的出来 i j k 后怎么判断呢?

使用特权

评论回复
14
peigang| | 2010-4-12 13:20 | 只看该作者
代码很精练
执行起来时间很长啊

使用特权

评论回复
15
流行音乐|  楼主 | 2010-4-12 14:20 | 只看该作者
14# lenmon650

我也想过这种方式,但是没想出来具体方法。你有没有具体的思路,能介绍一下吗?

使用特权

评论回复
16
流行音乐|  楼主 | 2010-4-12 14:25 | 只看该作者
本帖最后由 流行音乐 于 2010-4-12 14:57 编辑

15# handle09
如果这三个按键的x坐标有且只有两种不同数值,而且y坐标也有且只有两种不同数值,
则这三个按键位于某矩形的四个角上。

使用特权

评论回复
17
流行音乐|  楼主 | 2010-4-12 14:33 | 只看该作者
本帖最后由 流行音乐 于 2010-4-12 15:02 编辑

判断条件还可以再简化一下:
如果这三个按键的x坐标最多只有两种不同数值,且y坐标也最多只有两种不同数值,则这三个按键位于某矩形的四个角上。

使用特权

评论回复
18
流行音乐|  楼主 | 2010-4-12 14:36 | 只看该作者
16# peigang
循环次数为 n!/((n-3)!*3!) ,当n=10时,循环120次。当n=100时,循环161700
次。
我也觉得这个方法不够好,应该有更好的方法,只是还没找到。

使用特权

评论回复
19
wzf3151| | 2010-4-12 15:33 | 只看该作者
我咋感觉楼主的问题无解,我们是无法判断楼主所说的三个键同时按下的,无论采用什么算法。这不是个软件问题,似乎是个硬件问题啊。

我们所用的键盘是无法保证任意的按键组合都能被识别的。所以设计组合键时要注意组合的键是否位于了同一个输入口。
==============================================================
由于键盘本身结构的特殊性,键盘键位冲突是无法避免的,现在世界上所有键盘都存在键位冲突问题.

使用特权

评论回复
20
lxyppc| | 2010-4-12 18:02 | 只看该作者
楼主不妨换个角度看问题
我这样来描述你的问题
按键扫描,分为行扫描和列扫描
一个“完整干净”的列扫或一个“完整干净”的行扫确定唯一的一组按键
如果在一组按键中,相同的列扫描线对应了多个按键,并且相同的行扫描也对应了多个按键,则不能确定这组按键,也就是你题目中“是”的情况
“完整干净”的定义:所有的按键对不同的列扫描只使用一次,或所有的按键对不同的行扫描只使用一次

/**
    写一个最大X8键盘的测试代码,复杂度o(N)
*/

typedef struct  KeyCode{
    unsigned char X;
    unsigned char Y;
}KeyCode;

int CheckKey(KeyCode* pKey, int keyCnt)
{
    int i = 0;
    int x = 0;
    int y = 0;
    unsigned char XMap = 0;
    unsigned char YMap = 0;
    for(i=0;i<keyCnt;i++){
        if( ! ((1<<pKey.X) & XMap) ){
            // 如果这条X扫描线是干净的,则X计数值加
            x++;
        }
        if( ! ((1<<pKey.Y) & YMap) ){
            // 如果这条Y扫描线是干净的,则Y计数值加
            y++;
        }
        //标记这条X扫描线是脏的
        XMap |= (1<<pKey.X);
        //标记这条Y扫描线是脏的
        YMap |= (1<<pKey.Y);
    }
    // 如果x与keyCnt相同,则说明没有按键使用相同的行扫描
    // 如果y与keyCnt相同,则说明没有按键使用相同的列扫描
    // x,y任意一个与keyCnt相等,则可确定这组按键
    if(x == keyCnt || y == keyCnt){
        // 如果X或Y扫描线计数值与keyCnt相同,则说明没有冲突发生
        return 0;
    }
    // 否则发生冲突
    return 1;
}


/**
根据楼主写的测试用例1表示是,表示否
输出为:  
1
1
1
0
0
0
*/

#include "stdio.h"
KeyCode key1[] = {{4,0},{1,2},{4,2}};
KeyCode key2[] = {{2,1},{1,2},{2,2}};
KeyCode key3[] = {{1,1},{3,1},{1,2}};

KeyCode key4[] = {{1,2},{2,2},{3,2},{4,2}};
KeyCode key5[] = {{1,2},{2,1},{3,1},{4,2}};
KeyCode key6[] = {{1,2},{2,2},{3,1},{4,0}};

int main()
{
    printf("%d\n",CheckKey(key1,3));
    printf("%d\n",CheckKey(key2,3));
    printf("%d\n",CheckKey(key3,3));

    printf("%d\n",CheckKey(key4,4));
    printf("%d\n",CheckKey(key5,4));
    printf("%d\n",CheckKey(key6,4));
    getchar();
    return 0;
}

P.S.
21楼也说了,即然你都得到这些按键的值了,用不着再用软件去判断了吧
如果你硬件上的限制让你得不到正确的键值,用软件也没办法判断出来

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

10

主题

375

帖子

1

粉丝