| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2270 人关注过本帖
标题:确定一个数在一个平面中的位置
只看楼主 加入收藏
skrot
Rank: 1
等 级:新手上路
帖 子:55
专家分:0
注 册:2008-2-16
收藏
 问题点数:0 回复次数:14 
确定一个数在一个平面中的位置
题为:
形如下表:
  bgColor=#ffffff border=1>
[font=Times New Roman]
0
1
2
3
4
5
6
0
0
2
5
9
14
20

1
1
4
8
13
19


2
3
7
12
18



3
6
11
17




4
10
16





5
15






6







[/font]
数从左下往右上依次加一,一直加下去,边上的数字为坐标,竖为纵坐标,横为横坐标,如15在表中(0,5),12在(2,2)。问:给一个数,写个算法和程序得到它在表中的坐标?   
    我的想法是,用一个一维数组存下第一列的数,再你待找数去与这数组中的数比较,找出与待找数最近的两个数做差,与较小的数的差即为横坐标,与另一个数的差再减个一就是纵坐标了,但不知怎么写出源码了,因为一直相加,数太大,我定义的是长整型,但却老是溢出,不知怎么处理了。
    求一个高效的算法和源码,并帮解决数据溢出的问题。
搜索更多相关主题的帖子: 平面 位置 
2008-03-04 13:18
qq116676921
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2008-3-4
收藏
得分:0 
你可以直接把数存入二维数组,然后通过在数组中查找相应的数当所查找数据与数组中某位相同时则数组下表即为所求
2008-03-04 14:47
無邪的睡脸
Rank: 2
等 级:等待验证会员
威 望:1
帖 子:344
专家分:13
注 册:2007-9-11
收藏
得分:0 
回复 2# 的帖子
直接存入不但浪费了空间,而且查询费时!
lz的意思应该是直接求得任意一数的位置!
2008-03-04 14:50
無邪的睡脸
Rank: 2
等 级:等待验证会员
威 望:1
帖 子:344
专家分:13
注 册:2007-9-11
收藏
得分:0 
我用数学方法帮助分析了下
其实这个问题可以抽象为求:分组数列中任意一元素在第几分组,如果知道了分组,再确定在分组中的位置就容易了!
如何分组?如下:
(0),(1,2),(3,4,5)......
就相当于把一斜行当一分组。
每一分组的首元素容易求出:m*(m-1)/2,m为第m个分组(从1开始计数).也就是lz所说的第1列的数.
如果能求出任意一数n所在的分组,就能直接算出其坐标了。下面求n所在的分组:
m*(m-1)/2<=n<m*(m+1)/2
==> (m-1/2)^2 <=2*n+1/4 < (m+1/2)^2  (^2代表平方)
==> m<=(2*n+1/4)^(1/2)+1/2 <m+1   (^(1/2)代表开方)
至此可以直接求出n所在的分组.程序应该很简单了吧!
2008-03-04 15:04
skrot
Rank: 1
等 级:新手上路
帖 子:55
专家分:0
注 册:2008-2-16
收藏
得分:0 
谢谢楼上诸位大侠
刚回来看回贴,又想了两个小时,又想了点,程序还没写好,还在调试中,好了发出来。
    看了上面大侠的回贴,让我又学不少,能不能又给个不同的思路让我又多学点。
    还有怎么处理数据溢出问题,不方便的话,给个链接也行

心中明了路向何方,前路自有一番风光。
     skroty@.cn
2008-03-04 16:24
skrot
Rank: 1
等 级:新手上路
帖 子:55
专家分:0
注 册:2008-2-16
收藏
得分:0 
还是按我自己的算法做的:
#include<stdio.h>
#define NUM 2000000000
main()
{    
    long a[42000];/*设个足够大的数组用来存(0,i)*/
    do
     {   
    long x=0,y=0,n,i=0;/*要在这定义变量,在上面定义的话就要在while(n>=a[i]&&a[i]<=NUM);后再定义一次,是因为要从0开始再次比对*/
    printf("请输入一个数\n");
    scanf("%ld",&n);
    do
     {
            i++;
       a[i]=i*(i+1)/2;
       if(n==0)
       printf("0在表中(0,0)");/*不知道怎么在计算中处理0,只好把它单列出来了*/
       if(n<a[i]&&n>0)/*一定要加n>0,不然会出BUG,输出“0在表中(随机数,随机数)”
          {
        x=n-a[i-1];
        y=i-x-1;
        printf("%ld在表中(%ld,%ld)\n",n,x,y);
           }
          /*if(n==a[i])
              printf("%ld在表中(0,%ld)\n",i);*//*去掉这的注释符,如输出(0,i)上的数就会出现两次输出的情形,这是我出的第一个BUG,改好后就出现0的问题*/
      }while(n>=a[i]&&a[i]<=NUM);        
      printf("\n");
       }while(getchar()!='\'');
}

心中明了路向何方,前路自有一番风光。
     skroty@.cn
2008-03-04 18:05
skrot
Rank: 1
等 级:新手上路
帖 子:55
专家分:0
注 册:2008-2-16
收藏
得分:0 
说了有两次输出的事,这里出现了,n被替换了的情况,能说说吗

心中明了路向何方,前路自有一番风光。
     skroty@.cn
2008-03-04 18:07
lonmaor
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:郑州
等 级:版主
威 望:75
帖 子:2637
专家分:6423
注 册:2007-11-27
收藏
得分:0 
验证了低阶的几列数,没发现错误。大家再验证下。
方法就是,用给出的数i依次减去1~n,直到i不大于n,减去一次,计数器加一。
若i减到最后,等于n了,则说明i的x坐标为0.
得到的计数器的值即为【斜行】的第一个数(0,1,3,6,10...)所在之y坐标。
程序代码:
#include <iostream>
#include <cstdlib>
using namespace std;

class XY {
public:
    long int x;
    long int y;
};

XY getXY(long);

int main()
{
    long i;
    cin>>i;
    cout<<i<<"的坐标是:"
        <<endl<<"X: "<<getXY(i).x
        <<endl<<"Y: "<<getXY(i).y
        <<endl;
    system("pause");
    return 0;
}

XY getXY(long i)
{
    XY xy;
    int num=0,cnt=0;
    while(i>num)
    {
        i-=num;
        cnt++;
        num++;
    }

    if (i==num)
    {
        xy.x = 0;
        xy.y = i;
    }
    else
    {
        xy.x = i;
        xy.y = cnt-i-1;
    }
    return xy;
}
2008-03-04 21:10
广陵绝唱
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:29
帖 子:3607
专家分:1709
注 册:2008-2-15
收藏
得分:0 
我来个简单点的
/*呵呵,这个简单点,是照你的表写的,不用求X求Y滴,那么麻烦*/
#include<stdio.h>
#define N 6
int main(void)
{
        int i,j,x;
        float a[N][N]={{0,2,5,9,14,20},
                       {1,4,8,13,19,21},
                       {3,7,12,18,21,21},
                       {6,11,17,21,21,21},
                       {10,16,21,21,21,21},
                       {15,21,21,21,21,21}};
        do
        {
                printf("请输入您要查询的数字(0~20):\n");
                scanf("\n%2d",&x);
                if(x<0||x>20)
                        printf("您输入的字符有误,请重新输入.\n\n");
        }
        while(x<0||x>20);
        for(i=0;i<N;i++)
               for(j=0;j<N;j++)
                       if(a[i][j]==x)
                               printf("您要查找的字符在 %d行 %d列\n",i+1,j+1);





       getchar();
}



PS:又测试了一下,发现第一行无法算出,再改改。

如果有哪位朋友帮改一下,更感激不尽。

再PS:终于弄明白了,呵呵,改正过来了,现在测试没有错误了。

[[it] 本帖最后由 广陵绝唱 于 2008-3-4 22:37 编辑 [/it]]
2008-03-04 22:13
skrot
Rank: 1
等 级:新手上路
帖 子:55
专家分:0
注 册:2008-2-16
收藏
得分:0 
呵呵,再次感谢诸位大侠,让我学到了不少。

心中明了路向何方,前路自有一番风光。
     skroty@.cn
2008-03-05 00:26
  • 15
  • 1/2页
  • 1
  • 2
快速回复:确定一个数在一个平面中的位置
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.044088 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved