建议使用以下浏览器,以获得最佳体验。 IE 9.0+以上版本 Chrome 31+ 谷歌浏览器 Firefox 30+ 火狐浏览器
请选择 进入手机版 | 继续访问电脑版
设置昵称

在此一键设置昵称,即可参与社区互动!

确定
我再想想
选择版块

krissi

发帖: 1粉丝: 0

级别 : 新手上路

Rank: 1

发消息 + 关注

发表于2019-2-18 22:14:52 2728 17 楼主 显示全部楼层
[活动/公告] 针对活动“寻找超级算法大师-DevCloud赛道”最佳代码的挑战

关于活动:【开发者英雄大会】寻找超级算法大师-DevCloud赛道

地址:https://bbs.huaweicloud.com/forum/thread-13282-1-1.html


补充原题目如下:

题目
输入一个日期,格式为xxxx-xx-xx(年-月-日),计算其距离 2016-12-22 的天数。
//2016-12-22是DevCloud的生日哦~
 
示例1
Input:2018-12-22
Output:730
 
示例2
Input:2020-12-22
Output:1461


我认为,这类以算法取胜的比赛,应当公布源代码。


只可惜,我回贴以及私信管理员后,活动组织方只公布了“一等奖获得者的算法解题思路”,如下:

/**程序说明: 
**      本程序实现0~9999年任意时间与2016-12-22的天数差。
**      本程序除I/O方法为库函数外,其余一切函数均为自主实现(包括常用的算术类,阶乘等函数)。
**      可测试多组数据。 
**主要思想以及算法:
**      利用字典法+补偿法。先计算出目标日期与定点日期的年份差。然后计算出相差的年份中有多少个闰年(记为补偿)。
**      2016-12-22已经度过的天数为偏置(bias),最终天数差sum= 年份差*365 +字典月份的天数+偏置(bias)+补偿。
**      核心代码算法复杂度为O(1)。 
**模型假设: 
**      1、本程序假定平年有365天,闰年366天,不考虑特殊情况(如:1582年10月少了10天的情况) 。
**         2、默认输入日期小于2016-12-22的。相隔天数以负数输出。
**      3、输入数据格式请严格准守XXXX-XX-XX的格式,否则程序将数据判断为非法输入。并输出:Error data的提示 
**程序流程:
**      1、输入数据。
**      2、数据格式转化(将输入的字符串转化为整型数据) 
**      3、判断数据是否非法(如月数<1。天数为负数,等等)。 
**      4、计算并输出结果。
**程序拓展:
**      可将代码中的硬编码-定点日期(2016-12-22)改为用户输入时,可在O(1)的时间内计算任意2个日期之间天数。 
**/


可惜,没有代码。


根据公布的一等奖的解题思路,可以得知:

  1. 使用了“阶乘”这种代价较大的函数(虽然是自己写的)

  2. 使用了月份天数字典


修改:

我的代码在数学优化阶段出错了,就不贴了。


期待官方公布一等奖的源代码,非常想对比学习下。

回复 举报
分享

分享文章到朋友圈

分享文章到微博

柒仟

发帖: 2粉丝: 3

级别 : 版主

Rank: 7Rank: 7Rank: 7

发消息 + 关注

发表于2019-2-19 10:17:15 沙发 显示全部楼层

krissi,您好:

    对于算法的评估结果对您造成困扰,深表歉意!

    在对算法进行评估时,我们是按照测试用例通过率、思路独特性、实现精简度、算法时间复杂度、算法空间复杂度等维度综合评估,其中测试用例通过率为首要指标。

    除了基础用例,我们也增加了异常输入用例,纳入用例通过率评估。

    另,一等奖的源码公布已与作者沟通,暂未收到答复,请耐心等待。

感谢您对本次活动的支持,谢谢~

点赞 回复 举报

krissi

发帖: 1粉丝: 0

级别 : 新手上路

Rank: 1

发消息 + 关注

发表于2019-2-19 11:32:13 板凳 显示全部楼层
柒仟 发表于 2019-2-19 10:17 krissi,您好:    对于算法的评估结果对您造成困扰,深表歉意!   &n ...

没什么困扰,只是觉得奇怪而已。

想不通计算个日期差为什么会用到阶乘而已。


针对你说的“异常输入用例纳入用例通过率评估”这点我不认可。

任何算法竞赛,无论是蓝桥杯还是 ACM 竞赛,都是在假定输入用例完全正确的前提下进行的,否则算法竞赛就没有意义了。我相信华为有很多同事当年参加过各种算法竞赛,这个常识,随便问任何一个参加过算法竞赛的人都知道。同时,可以去任何一个 oj 系统下测试,比如航电的 http://acm.hdu.edu.cn 、北大的 http://poj.org ,都不用检查输入用例是否符合要求,这是常识。


点赞 回复 举报

柒仟

发帖: 2粉丝: 3

级别 : 版主

Rank: 7Rank: 7Rank: 7

发消息 + 关注

发表于2019-2-19 14:14:38 地板 显示全部楼层

   

krissi 发表于 2019-2-19 11:32没什么困扰,只是觉得奇怪而已。想不通计算个日期差为什么会用到阶乘而已。针对你说的“异常输入用例纳入 ...

非常感谢您所提出的意见,我们在后续类似活动中,会按照您的意见优化算法评估规则,感谢~

一等奖的算法内容,我们会在征得作者同意之后在活动贴中公布,请您理解~

再次感谢您对活动的支持,谢谢!

点赞 回复 举报

what is ti...

发帖: 0粉丝: 0

级别 : 新手上路

Rank: 1

发消息 + 关注

发表于2019-2-19 20:30:08 5# 显示全部楼层

上周末,我看到我的代码被选为一等奖,倍感荣幸。之后私信了比赛的版主,版主态度也很好。

中午看到有留言要公布代码,然后就顺着链接点了进来,发现遇到了一只半瓶咣当,喜欢抬杠,钻牛角尖的键盘侠,略感不适,特此留言。


1.你说要公布代码,仅供学习使用,完全可以,马上我就回复那位比赛的版主,公布。


2.关于“阶乘”的讨论,你一开始要表达的意思是,我的代码使用了阶乘,效率不高,所以不配得一等奖。继比赛的版主回复你之后,你明白了原来我用的阶乘是做输入检测的,你又开始抬杠,说什么,要保证输入用例完全正确,输入检测是多余的,反正就是要证明一等奖代码太low,你的代码才天下第一,有种怀才不遇的郁闷之情。那我就很好奇你的代码有多厉害。难道华为方评委都眼瞎?


3.我看了你自信满满贴出的那看似牛逼的代码,刚刚运行了一下。我就随便输入个日期1999-01-01,输出结果都是错的。错的。错的。请问你哪来的自信在这危言耸听?你也就欺负欺负外行,估计是因为比赛的版主是外行,被你的牛逼哄哄,不服的气势吓到了,才耐心回复了你。你见到有行内的人鸟你一句么?!人要有自知之明...


4.像你这种键盘侠,我在网上遇到多了,见怪不怪。我总结一下你们特有的清奇的脑回路:

   1)我写的代码很好,应该得第一。

   2)比赛结果出来后,发现第一不是自己,心急了,比赛会不会是内定的噱头。

   3)于是以种种冠冕堂皇的理由要求公布完整代码。完整的思路给你了,都不接受。。非要完整代码跑一遍,真是"聪明"到家了

   4)公布代码之后,开始继续鸡蛋里挑骨头,我这里写的比他好,他那里写的没我好。

   5)最后吐槽,垃圾比赛,垃圾评委。。自我得意


最后补充一点:一个程序连对数据的预处理都不做,还好意思说自己是程序员?井底之蛙,嘤嘤狂吠罢了。可悲可叹


公布代码,仁至义尽,到此为止,不想和键盘侠多逼逼一句


点赞1 回复 举报

krissi

发帖: 1粉丝: 0

级别 : 新手上路

Rank: 1

发消息 + 关注

发表于2019-2-20 13:43:27 6# 显示全部楼层

   

柒仟 发表于 2019-2-19 14:14   非常感谢您所提出的意见,我们在后续类似活动中,会按照您的意见优化算法评估规则,感谢~一等 ...

基于公布的获奖代码,我认为:

整理每个用户的算法的同事,移交给评判算法的同事,然后评判完毕后再将结果移交回来,这个过程的某个环节,出了问题,很可能导致了获奖代码与获奖用户错位的情况。

因为我觉得,公布的获奖代码真的太业余了,具体问题随便一个曾经参赛过的选手都应该能看出来,我不相信参加华为活动的数百名选手的最高水平就是这样子的,毕竟用华为云的用户很多都是码农。


举例一等奖作品的致命错误:

		char data[10];//储存输入的日期.

获奖代码居然用这个字符数组保存"2016-12-22"这样的字符串,必然会导致数组越界。这是任何一个 C 语言初学者都不应该犯的初级错误。我不相信华为负责评奖的工程师能忽视这么简单的致命错误,所以我觉得,是某个环节导致了获奖作者搞错的情况。


5# 指出了我的代码的错误,非常感谢,的确这是我的疏忽,我在进行数学优化的时候,错误了将计算机特有算法进行了数学优化,导致了在某些日期的计算上差 1 天。错误的算法不应该获奖,取消我的二等奖获奖资格吧,我没有意见。我相信有人肯定做出了正确的优化,毕竟使用华为云的很多人都是码农。


那么多参赛者,我相信会有更优秀的代码有资格拿一等奖。

(ps:希望评选的新的一等奖不要再检查什么输入条件了,真的太业余了)


点赞 回复 举报

krissi

发帖: 1粉丝: 0

级别 : 新手上路

Rank: 1

发消息 + 关注

发表于2019-2-20 13:55:54 7# 显示全部楼层

   

what is time? 发表于 2019-2-19 20:30上周末,我看到我的代码被选为一等奖,倍感荣幸。之后私信了比赛的版主,版主态度也很好。中午看到有留言要 ...

谢谢你指出我的错误,的确是我的疏忽。我做数学优化的时候考虑欠妥了。


我提出“阶乘”问题的时候,还没看到你的代码。即便看了你的代码之后,我仍然认为“转换字符串为数字时使用阶乘”是非常差的算法。不信你去问问其他蓝桥杯或 ACM 参赛选手?如果需要,我可以几分钟写出来一个,不用阶乘。这都是最早学编程时候的基础题目吧,我记得书本上都有这样的课后题。还有用 char data[10] 保存“2016-12-22”这种错误更是初学者都不应该犯的。


显然你没参加过其他竞赛,我也就不多说什么了。交流编程而已,至于这么激动么。

点赞 回复 举报

nba_my_tim...

发帖: 1粉丝: 0

级别 : 新手上路

Rank: 1

发消息 + 关注

发表于2019-2-21 15:44:21 8# 显示全部楼层

   

what is time? 发表于 2019-2-19 20:30上周末,我看到我的代码被选为一等奖,倍感荣幸。之后私信了比赛的版主,版主态度也很好。中午看到有留言要 ...

我也是希望能见到代码公布的。倒不是扛精,只是希望可以交流学习。

你的算法代码确实精简,大部分思路是相同的。对比一下,我的算法比你稍差一些,但思路比较简单易懂。互相学习探讨交流,谢谢。

#include <iostream>

using namespace std;
static int MONTH_DAY[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
static const int LeapYearDay = 366;
static const int NormYearDay = 365;
const int   datestrLen = 11;
//判断某年是否为闰年:
bool IsLeapYear(int year)
{
    return ((year & 3 == 0 && year % 100 != 0) || year % 400 == 0);
}
//截取字符串数组的子字符串转成整数
int SubStringToInt(char *src, int index, int length)
{
    src = (src + index);
    int res = 0;
    for(int idx=0;idx<length;idx++)
    {
        if (*src >= '0' && *src <= '9')
        {
            res = (*src++ - '0')+ (res <<3)+ (res << 1)  ;
        }
    }
    return res;
}
//检测字符串长度并且是否为有效数字
int ValidStrLength(char * str)
{
    int len = 0;
    while (*str)
    {
        if ((*str >= '0' &&*str <= '9')||*str=='-')
        {
            len++;
            *str++;
        }
        else
        {
            break;
        }
    }
    return len ;
}
//判断两字符串是否相等
int Equals(char * str1, char *str2)
{
    while ((*str1 ) || (*str2))
    {
        if (*str1++ > *str2++)
            return 1;
        else if (*str1++ < *str2++)
            return -1;
    }
    return 0;
}
//转换成有效的年月日
bool ConvertToDate(char* date_str, int& year, int& month, int& day)
{
    if (ValidStrLength(date_str)!=datestrLen-1) return false;
    year = SubStringToInt(date_str, 0, 4);
    month = SubStringToInt(date_str,5, 2);
    day = SubStringToInt(date_str, 8, 2);
    if (IsLeapYear(year)) {
        MONTH_DAY[2] = 29;
    }
    else
    {
        MONTH_DAY[2] = 28;
    }
    return year >= 0 &&
        (month <= 12 && month > 0) &&
        (day <= MONTH_DAY[month] && day > 0);
}
//当年日期是该年的第几天
int GetSequentDaysOfYear(int year, int month, int day)
{
    if (IsLeapYear(year))
        MONTH_DAY[2] = 29;
    else
        MONTH_DAY[2] = 28;
    for (int i = 0; i < month; ++i)
    {
        day += MONTH_DAY;
    }
    return day;
}
//计算某两日期之间的相差天数
int DatesDiff(char* date1, char* date2)
{
    int year1, month1, day1;
    int year2, month2, day2;
    if (!ConvertToDate(date1, year1, month1, day1) || !ConvertToDate(date2, year2, month2, day2))
    {
        cout << "输入的日期格式不符合规范\r\n";
        return -1;
    }
    if (year1 == year2 && month1 == month2)//如果年月相同
    {
        if (day1 > day2)
        {
            swap(day1, day2);
        }
        return  day2 - day1;
    }
    else if (year1 == year2)//仅年份相同
    {
        int diff1, diff2;
        diff1 = GetSequentDaysOfYear(year1, month1, day1);
        diff2 = GetSequentDaysOfYear(year2, month2, day2);
        if (diff1 > diff2)
        {
            swap(diff1, diff2);
        }
        return diff2 - diff1;
    }
    else //如果年月都不相同
    {
        if (year1 > year2)//确保year1年份早于year2
        {
            swap(year1, year2);
            swap(month1, month2);
            swap(day1, day2);
        }
        int diff1, diff2, diff3 = 0;
        //diff1=年份小的日期,距年底还有多少天;
        //diff2=年份大的日期是当年的第几天;
        //diff3=两个年份间相差的整年数,并换算成对应天数
        if (IsLeapYear(year1))
            diff1 = LeapYearDay - GetSequentDaysOfYear(year1, month1, day1);
        else
            diff1 = NormYearDay - GetSequentDaysOfYear(year1, month1, day1);
        diff2 = GetSequentDaysOfYear(year2, month2, day2);
        for (int year = year1 + 1; year < year2; year++)
        {
            if (IsLeapYear(year))
                diff3 += LeapYearDay;
            else
                diff3 += NormYearDay;
        }
        return diff1 + diff2 + diff3;
    }
}



int main()
{
    
    char  date1[datestrLen] = "2016-12-22";
    char  date2[datestrLen] =""  ;
    char  endflag[5] = "exit";
   
    while (Equals(date2, endflag) != 0)
    {
        cin.clear();
        cin.sync();
        cout << "Input the Date Format like '2018-02-02',Input 'exit' to quit the program" << endl;
        cin.getline(date2, datestrLen);
        if (Equals(date2, endflag) == 0)
        {
            break;
        }
        int diff_dates = DatesDiff(date1, date2);
        cout <<"["<< date1 << "]与[" << date2 << "]相差{" << diff_dates << "}天" << endl;
    }
    return 0;

}


点赞 回复 举报

yw80

发帖: 1粉丝: 0

级别 : 注册会员

Rank: 2

发消息 + 关注

发表于2019-2-21 23:09:28 9# 显示全部楼层

   

nba_my_time 发表于 2019-2-21 15:44   我也是希望能见到代码公布的。倒不是扛精,只是希望可以交流学习。你的算法代码确实精简,大 ...

同为曾经的竞赛选手,我不理解你对获奖的这种垃圾代码何必留情面?
你的代码我看一遍就知道水平很高了。不说别的,仅 SubStringToInt 这个函数能看懂的人怕是都不多。


对于获奖代码,我的观点:就是一坨 shit。随便扫了一眼,问题列举如下:

 

0. 代码格式就是一坨 shit。当然,这不是格式比赛,这个我就当没看见。

 

1. 第 45 行与 49 行:

   char data[10];//储存输入的日期. xxxx-xx-xx
   ……
   while(gets(data)){

这种内存越界问题都能写出来,这是猴子派来的逗逼么?
这种代码是灾难性的。即便运行不出错,这也是一个可以直接打入死牢的 bug!
这种 bug,别说 IT 从业者了,就连大一新生都能看出来吧。从业者要是写出来这种 bug,可以卷铺盖走人了。

 

2. 第 6 行:

static int MyPow(int a,int b){

请告诉我对全局函数加 static 的意义是什么?

 

3. 第 15 行与第 44 行:

    int day[]={31,28,31,30,31,30,31,31,30,31,30,31};
    ……
    int dictionary[N]={0,31,59,90,120,151,181,212,243,273,304,334};

这么简单的小程序居然定义两个意义相似的数组做字典用,空间浪费的问题就不考虑了吗?

 

4. 第 14 行:

bool judge(const int year,const int month,const int days,bool flag){

这个 const 的意义是什么?
如果作者知道 const 的意义是什么,为什么参数 flag 不加 const?为什么 MyPow 函数的参数不加 const?
代码没问题,产生这种情况的背后原因才是问题。

 

5. 第 46、47、48 行:

    int year=0,mon=0,days=0,……
    bool  flag2;// 判断当前是否为闰年
    int flag,flag1;    //补偿天数。

year, mon, days……
flag、flag1、flag2……
小学生变量命名法。当然,变量命名不影响结果正确性,觉得恶心的闭眼就好了。

 

6. 第 18~41 行:

/*辅助函数,阶乘方法(由于不能是用第三方类,所以只能自己写阶乘类了)*/
static int MyPow(int a,int b){
    int sum=1;
    for(int i=0;i<b;i++){
        sum*=a;
    }
    return sum;
}
/*将输入的字符串利用1次遍历转化为3个整型数据,偏于后续计算。*/
void  TurnStringToInt(char *string,int length,int *year,int *mon,int *day){
    int flag=0;
    int count=0;
    *year=0;//由于要实现多个测试数据,所以必须重置year,mon,day. 
    *mon=0;
    *day=0;
    for(int i=length-1;i>=0;i--){
        if(string!='-'){
            if(flag==0){
                (*day)+=(int)(string-'0')*MyPow(10,count++);
            }else if(flag == 1){
                (*mon)+=(int)(string-'0')*MyPow(10,count++);
            }else{
                (*year)+=(int)(string-'0')*MyPow(10,count++);
            }
             
        }else{
            flag++;
            count=0;
        }
         
    }
}

有史以来最垃圾的字符串转数字算法,没有之一。
别怪我喷。看看 8# 的代码,13~26 行是怎样转换字符串为数字的,我估计获奖者八成看不懂。估计他还陶醉在自己用阶乘转换的“美妙”算法中吧。

 

7. 作为核心算法的求日期差的函数在哪???
真没有,这些代码像 shit 一样糊在了 main 里面。我都难以想象出来他调试时候的痛苦表情。

 

8. 代码浪费了大量的空间,却连最基本的空间换时间的概念都不知道,随处可见 day[month-1] 这种写法。(推荐写法参见 8# 第 4 行)

 

9. 第 19 行:

void  TurnStringToInt(char *string,int length,int *year,int *mon,int *day){

作为开发常识,如果函数没有对字符串进行写入,是不需要传入长度参数的。这个函数就是典型的违背开发常识的写法,函数没有对 char *string 做任何写入处理,却还要用 length 参数为 char *string 指定长度。PS:居然敢用 string 当作参数名字,无知者无畏啊。


10. 第 5~12 行:

/*辅助函数,阶乘方法(由于不能是用第三方类,所以只能自己写阶乘类了)*/
static int MyPow(int a,int b){
    int sum=1;
    for(int i=0;i<b;i++){
        sum*=a;
    }
    return sum;
}

这明明是一个求 a 的 b 次幂函数,为什么作者非说这是阶乘函数呢?



综上:这个一等奖,怕是不敢参与讨论吧。

 

点赞 回复 举报

yw80

发帖: 1粉丝: 0

级别 : 注册会员

Rank: 2

发消息 + 关注

发表于2019-2-21 23:22:23 10# 显示全部楼层

坐等获奖者的解释

点赞 回复 举报

游客

您需要登录后才可以回帖 登录 | 立即注册