作业|学习资料|投稿|算法|题解

程序设计-寒假作业3052再解

skyrim · 2月6日 · 2017年 358次已读

一个更加便捷的方法:

先对输入的数字加一(increase函数),然后判断是不是不重复数(istarget函数)。如果不是,结束;否则,(modify函数)从左往右遍历数组,在重复的第二位加一(同时考虑进位问题),后面的所有数字按“0101”重复,因为要最小,所以最高位设为“0”。

这里我把“9”这个特殊的数字单独考虑,因为它的进位比较麻烦,这也是我的代码很长的原因。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define FULL '9'+1
int istarget(char c[])  //判断是否为目标
{
    int i;
    for (i=0;i+1<strlen(c);i++)
        if (c[i]==c[i+1])
        return 0;
    return 1;
}
int all9(char c[])//判断输入的数字是否全部为9
{
    int i;
    for (i=0;i<strlen(c);i++)
        if (c[i]!='9')
        return 0;
    return 1;
}
void increase(char c[])
{
    int i=strlen(c)+1;
    int j;
    if (all9(c))//全部为9的话会使数组长度加一,所以单独考虑
    {
        for (j=1;j<i;j++)
            c[j]='0';
        c[0]='1';
    }
    else//否则就最后一位加一,从后往前遍历,如果该位为满(FULL),那么前一位加一
    {
        i=strlen(c)-1;
        c[i]++;
        for (;i>0;i--)
        {
            if (c[i]==FULL)
                {
                    c[i]='0';
                    c[i-1]++;
                }

        }
    }
}
void modify(char c[])
{
        if (c[0]=='9'&&c[1]=='9')//如果加一后是以“99”开头,那么也会使数组长度加一,
                           //所以也单独考虑
        {
            int i=strlen(c)+1;
            int j=0;
            c[j]='1';
            for (j=1;j<i;j++)
            {
                if (j%2==1)
                    c[j]='0';
                else
                    c[j]='1';
            }
        }
        else
        {
            int i=0;
            char prev,latt;
            for (i=0;i+1<strlen(c);i++)
            {
                prev=c[i];
                latt=c[i+1];
                if (prev==latt)//一旦找到重复的两个数字就可以开始操作了
                {
                    if (prev=='9')//如果重复的数字是9,同样单独考虑
                    {
                        c[i-1]++;
                        if ((strlen(c)-i)%2==0)//按照从第一个重复数字到最后一位有
                                         //多少数字的奇偶分类讨论
                        {
                            for (;i<strlen(c);i+=2)
                            {
                                c[i]='0';
                                c[i+1]='1';
                            }
                        }
                        else
                        {
                            c[i++]='0';
                            for (;i<strlen(c);i+=2)
                            {
                                c[i]='1';
                                c[i+1]='0';
                            }
                        }
                    }
                    else//否则就不存在进位问题
                    {
                        c[++i]++;
                        i++;
                        if ((strlen(c)-i)%2==0)
                        {
                            for (;i<strlen(c);i+=2)
                            {
                                c[i]='0';
                                c[i+1]='1';
                            }
                        }
                        else
                        {
                            c[i++]='0';
                            for (;i<strlen(c);i+=2)
                            {
                                c[i]='1';
                                c[i+1]='0';
                            }
                        }
                    }
                    break;
                }
            }
        }
        if (!istarget(c))//这里的递归是为了避免输入的数字为679898->679899->679901而错误
            modify(c);
}
void solve(char c[])
{
    increase(c);
    if (!istarget(c))
        modify(c);
}
int main()
{
    int i,cas;
    char restore[1000];
    scanf("%d",&cas);
    for (i=0;i<cas;i++)
    {
        memset(restore,0,1000);
        scanf("%s",restore);
        solve(restore);
        printf("case #%d:\n",i);
        printf("%s\n",restore);
    }
return 0;
}

程序设计-寒假作业3052又解

2017-2-6 0

程序设计-寒假作业3052再解

2017-2-6 0

说点什么

avatar

您可以根据需要插入表情、图片、音频、视频或者其他附件,也可以 @ 你需要提及的用户

  
不开心么么什么再见加油发火可以可怜可爱吐吐血吓呵呵哈哈哦哭哼喜欢嗯嘿嘿困圣诞坏笑圣诞调皮坏笑女汉子奸笑好的委屈宝宝害羞小清新心塞快哭了恭喜发财惆怅我最美抓狂抠鼻放空无奈晕汗泪奔温柔女生狗年生气笑笑泪衰调皮调皮女生鄙视酷静静额鼓掌
上传图片
 
 
 
上传视频和音频
 
 
 
上传其他类型文件
 
 
 
  订阅评论动态  
提醒