笔趣阁 //www.boquge.com/book/105094/ 为您提供编程之战全文阅读！注册本站用户，获取免费书架，追书更方便！
“系统正在销毁矩阵...”
“系统重新构建矩阵...”
“系统生成杨氏矩阵...”
“初始化设置：长度100万单位，宽度100万单位...”
“随机化生成target...”
听到这熟悉的声音，杨成皱了皱眉头。
他朝下方一看，只见那密密麻麻的矩阵，延伸到虚拟世界的尽头，漫无边际。
那一个个犹如针孔般的矩阵格子，足以让有“密集恐惧症”的人抓狂。
“呵...好家伙”。
杨成不禁倒吸一口凉气。
100W乘以100W，绝对是天文数字啊。
尼奥这次算是下了血本了。
地毯式搜索，面对这个数量级的问题，只会如同泥牛入海一般，杳无音讯。
对于搜索问题，查找次数必须限制在百万级，才会有较好的用户体验。
悬浮在高空中，杨成用手托着下巴，开始了思考。
系统刚才有提到“杨氏矩阵”。
这是个什么东西呢？
对于杨氏矩阵中任意一个小格子，它里面存放有数字元素。
小格子右边和下方的元素都比它自身要大。
或者说，对于矩阵，任意一行，任意一列元素都是严格的增序。
比如像这样：
“1，5，9”
“2，6，10”
“3，7，11”
这就是一个杨氏矩阵。
它不管哪一行，哪一列，都是严格递增的。
根据这个性质，不难推出（也可以观察出）：
对于任意元素，它左边的元素比它小，下边的元素比它要大。
所以，如果要在杨氏矩阵中查找某个元素，可以利用这个性质，从矩阵最右上方开始查找。
比如如果我要找“3”，我从右上角的“9”开始查找。
因为“3”小于“9”，所以找“9”左边的（左边的元素比它小），得到“5”。
“3”又小于“5”，所以找“5”左边的，得到“1”。
“3”大于“1”，找“1”下边的（下边的元素比它要大），得到“2”。
“3”大于“2”，找“2”下边的，命中目标。
这个算法效率很高，足以胜任长宽（size）上百万的矩阵查找。
对于这个问题，即使是最坏的情况，即尼奥位于矩阵的最左下方，而从最右上方查找，也只需要200W次查找，这是程序足以胜任的。
不过，如果尼奥如果不在矩阵中，最后查找就会越界，即非命中查找。
杨成编写完代码，然后一提交。
只见天边宛如大潮涌来，成片成片的矩阵格子倒塌，化为废墟。
就如同被掰开的巧克力一般，矩阵分崩离析。
估摸着过了几分钟。
刚才还气势恢宏的矩阵，通通变成了断壁残垣。
某处废墟，一堆破铜烂铁里突然伸出一只手臂，手上还举着一支小小的白旗。
“墨菲斯，你赢了”。
“叮！当前积分181分，击败了全球47%的玩家，请您再接再厉！”
“系统重新构建矩阵...”
“系统生成杨氏矩阵...”
“初始化设置：长度100万单位，宽度100万单位...”
“随机化生成target...”
听到这熟悉的声音，杨成皱了皱眉头。
他朝下方一看，只见那密密麻麻的矩阵，延伸到虚拟世界的尽头，漫无边际。
那一个个犹如针孔般的矩阵格子，足以让有“密集恐惧症”的人抓狂。
“呵...好家伙”。
杨成不禁倒吸一口凉气。
100W乘以100W，绝对是天文数字啊。
尼奥这次算是下了血本了。
地毯式搜索，面对这个数量级的问题，只会如同泥牛入海一般，杳无音讯。
对于搜索问题，查找次数必须限制在百万级，才会有较好的用户体验。
悬浮在高空中，杨成用手托着下巴，开始了思考。
系统刚才有提到“杨氏矩阵”。
这是个什么东西呢？
对于杨氏矩阵中任意一个小格子，它里面存放有数字元素。
小格子右边和下方的元素都比它自身要大。
或者说，对于矩阵，任意一行，任意一列元素都是严格的增序。
比如像这样：
“1，5，9”
“2，6，10”
“3，7，11”
这就是一个杨氏矩阵。
它不管哪一行，哪一列，都是严格递增的。
根据这个性质，不难推出（也可以观察出）：
对于任意元素，它左边的元素比它小，下边的元素比它要大。
所以，如果要在杨氏矩阵中查找某个元素，可以利用这个性质，从矩阵最右上方开始查找。
比如如果我要找“3”，我从右上角的“9”开始查找。
因为“3”小于“9”，所以找“9”左边的（左边的元素比它小），得到“5”。
“3”又小于“5”，所以找“5”左边的，得到“1”。
“3”大于“1”，找“1”下边的（下边的元素比它要大），得到“2”。
“3”大于“2”，找“2”下边的，命中目标。
这个算法效率很高，足以胜任长宽（size）上百万的矩阵查找。
对于这个问题，即使是最坏的情况，即尼奥位于矩阵的最左下方，而从最右上方查找，也只需要200W次查找，这是程序足以胜任的。
不过，如果尼奥如果不在矩阵中，最后查找就会越界，即非命中查找。
杨成编写完代码，然后一提交。
只见天边宛如大潮涌来，成片成片的矩阵格子倒塌，化为废墟。
就如同被掰开的巧克力一般，矩阵分崩离析。
估摸着过了几分钟。
刚才还气势恢宏的矩阵，通通变成了断壁残垣。
某处废墟，一堆破铜烂铁里突然伸出一只手臂，手上还举着一支小小的白旗。
“墨菲斯，你赢了”。
“叮！当前积分181分，击败了全球47%的玩家，请您再接再厉！”