作业

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

jxtxzzw · 2月6日 · 2017年 326次已读

本文写于 2017年02月06日,距今已超过 1 年,距 2018年11月02日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


本题另有2种解法,参阅《程序设计-寒假作业3052》、《程序设计-寒假作业3052再解》。


sp170206_162757

从数学角度,这是易证的。

如果一个数字有多组重复,那么最左边的那组重复,是肯定要被处理掉的,也就是最左边两个重复的数字,一定会做一次加1,于是右边所有的数字都变成0。可是变成0之后,0本身成看重复数字,所以为了保证最小,应该把0变成0101的交替。

柳天奕经过尝试,写出了他的代码,顺利通过OJ,详细可阅读他的题解:程序设计-C语言程序设计基础-寒假作业3052再解》。

我发现,整个程序实际上可以进一步简化。

于是我也动手写了一份,经测试正确。

下面慢慢来说。

首先要从左往右找到重复的两个数,那就逐个字符比较,可以有一个last表示上一位,一个current表示当前位,last==current就说明有重复,否则,继续往下比较。

等等,如果是个位数,怎么办?

个位数没有办法弄出last和current。不过不要紧,个位数一定不会是重复的。

因此直接加1就可以输出。即使遇到9,需要进位,变成10,10也是正确的答案。

这样一来,思路就很清楚了。

if ( strlen ( st ) == 1 ) {

} else {

}

先来填个位数。

取出那一位,加1,输出。

为了方便进位,这里可以直接把字符变成数字,加1,那么数字9加1变成数字10,也就不需要处理进位了。

if ( strlen ( st ) == 1 ) {
    printf ( "%d" , st[0] - '0' + 1 );

} else {

}

接着写else的部分。

pos是用来记录当前处在字符串的哪一个position,因为至少会有2个字符,所以st[1]必存在,pos直接初始化为1,last为st[0],current为st[1]。

pos = 1;
last = st[pos - 1];
current = st[pos];

接着是比较。

if ( last == current ) {

} else {

}

如果last和current是一样的,就说明这是重复的数字,那么按照上文的分析,就应该把字符串从头到current之前照常输出、把current加1、把current之后的变成010101……

照常输出的部分比较简单。

for (int i=0;i<pos;i++){
    printf("%c",st[i]);
}

cuurent加1,就有可能产生进位,这里先不考虑进位。

printf("%c",st[pos]+1);

后面是输出010101……

循环的条件是容易控制的,就是从pos+1位一直到小于strlen。

关键是怎么控制0和1交替?

似曾相识?

有一个小技巧,在Pascal中比较常见。

这是因为Pascal有“前驱”和“后继”的概念,所以常用这种方法交换TRUE和FALSE。

一个整数p,做|p-1|,就可以完成0和1的交替。

比如p=1,p-1就是0,取绝对值,就是0,这时p=0,p-1就是-1,取绝对值就是1,这时p=1……如此循环往复。

由于要最小的不重复数,所以是0和1的交替,而不是1和0的交替,因此p从0开始。

int p = 0;
for ( int i = pos + 1; i < strlen ( st ); i++ ) {
    printf ( "%d", p );
    p = abs ( p - 1 );
}

如果是C语言,大概不会首先想到这种方法,而是会想到利用奇偶性,就是除以2取余数。

首先令cnt=strlen(st)-pos-1,然后for循环从0到小于cnt。

循环体输出i除以2的余数,即输出(“%d”,i%2)。

比如i为0,0%2=0,输出0,接着i为1,1%2=1,输出1,接着i为2,输出0……

printf ( "%d", i % 2 );

再不然。

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';
    }
}
}

到这里,last==current的事情就做完了。

if ( last == current ) {
    for ( int i = 0; i < pos; i++ ) {
        printf ( "%c", st[i] );
    }

    printf ( "%c", st[pos] + 1 );
    int p = 0;

    for ( int i = pos + 1; i < strlen ( st ); i++ ) {
        printf ( "%d", p );
        p = abs ( p - 1 );
    }

} else {

如果不等,就要比较下一个。

于是pos就要加1,然后重新定last和current。

} else {
    pos++;
    last = st[pos - 1];
    current = st[pos];
}

那pos加到什么时候结束?

比完整个字符串就结束,也就是说,外面还要套一层循环,终止的条件是pos==strlen。

pos = 1 ;
last = st[pos - 1];
current = st[pos];

while ( pos < strlen ) {
    if ( last == current ) {

    } else {
        pos++;
        last = st[pos - 1];
        current = st[pos];
    }
}

这时我们看到,last和current的赋值重复了,所以还可以进一步合并,以消除“代码复制”这一不良的做法。

除此以外,循环不仅由pos==strlen退出,还要可以提前break,这是因为我找到了最前面的那个重复数字,就可以输出正确答案,循环就到此为止了。

所以,在输出0101交替之后,要加上break。
“`if ( strlen ( st ) == 1 ) {
printf ( "%d"st[0] – '0' + 1 );

} else {
pos = 1;

<pre><code>while ( pos < strlen ) {
last = st[pos – 1];
current = st[pos];

if ( last == current ) {
for ( int i = 0; i < pos; i++ ) {
printf ( "%c", st[i] );
}

printf ( "%c", st[pos] + 1 );
int p = 0;

for ( int i = pos + 1; i < strlen ( st ); i++ ) {
printf ( "%d", p );
p = abs ( p – 1 );
}

break;

} else {
pos++;

}
}
</code></pre>

}“`
退出循环就产生了2种情况,如果pos==strlen,说明没有重复的,那么加1输出答案,如果pos!=strlen,说明已经发现重复数字,并且输出了结果,就不需要做什么了。

加1输出结果,意思是,从第0位到最后一位之前照抄,然后最后一位加1输出。(不考虑进位)
“`if ( pos == strlen ( st ) ) {
for ( int i = 0; i < pos – 1; i++ ) {
printf ( "%c", st[i] );
}

<pre><code>printf ( "%c", st[pos – 1] + 1 )
</code></pre>

}“`
到这里为止,我们把所有可能的情况都处理掉了,只剩下进位这件事。

进位是由加1引起的。

加1也是个大麻烦,因为会产生很多可能。

第一种是最令人放心的,加1,没有影响任何东西,比如34,加1,变成35,很好。

第二种是稍微复杂点的,就是进位。

进位又包括两种,一种是总位数不变,也就是需要进位的9不在最高位,比如39,进位变成40,另一种是需要进位的9在最高位,进位以后整个数字的位数增加,比如9,进位变成10,由1位数变成2位数。

第三种是最令人头疼的,就是加1以后产生新的重复数。

比如43,加1,变成44,又比如2199,加1,变成2200。

我们先来考虑pos==strlen这段代码里的进位。

其中第一种情况是最好处理的,上面的代码不用变。从第0位到最后一位之前照抄,然后最后一位加1输出。

pos==strlen的时候,第二种情况就被简化了。

因为对于9来说,个位数的9,加1,进位,变成10,而这一点在之前就已经被解决掉了,非个位数的9,那就是99、999之类的会有位数的变化,但是已经进入了pos==strlen,就不可能会有重复数字,因此这种情况也不需要考虑。

那么,对于类似19、39之类的,虽然有进位,不过也可以按照34+1=35这样操作。这时就不是“从第0位到最后一位之前照抄,然后最后一位加1输出”,而是“从第0位到最后第二位之前照抄,然后把最后两位当做整数,加1,输出”。

即,情况一和情况二,可以合并。

if ( pos == strlen ( st ) ) {
    for ( int i = 0; i < pos - 2; i++ ) {
        printf ( "%c", st[i] );
    }

    int d;
    sscanf ( ( st + pos - 2 ), "%d", &d );
    printf ( "%d", d + 1 );
}

这里运用到了sscanf(),之前没有接触过。

sscanf()和sprintf()是很强大的两个函数,尤其是当他们用「类似」正则表达式的格式控制符来输入和输出数据的时候。

如此强大的两个函数,想要掌握它们的全部功能,不是一时半会儿能解决的,因此这里只解释代码中用到的功能。

sscanf ( const char*, const char*, ... )

第一个参数,是读入数据的来源,来源要求是一个字符串。

因为我们想要从pos-2为开始读,有需要提供一个字符串,那么就可以用st+pos-2这种方法给一个字符串。

所以,第一个参数,我们写( st + pos – 2 )。

第二个参数,是格式控制符。

因为我们想要一个整数,是%d。

所以,第二个参数,我们写”%d”。

第三个参数开始,是读数据读到哪里,是一个地址,或者说,是一个基本数据类型的指针。

之前有了一个int d,那么这里就应该是&d,别忘了&。

所以,第三个参数,我们写&d。

简单说,这里用一个for循环输出到了pos-2之前,然后从pos-2这一位开始,把字符串以%d的形式,读入到一个int中,输出d+1。

第三种情况会产生新的重复数,所以在此之前,要把last==current那里遗留的进位问题处理掉。

也可以用类似的方法解决。
“`for ( int i = 0; i < pos – 1; i++ ) {
printf ( "%c", st[i] );
}

int d;
sscanf ( ( st + pos – 1 ), "%d", &d );
printf ( "%d", d + 1 );
int p = 0;

for ( int i = pos + 1; i < strlen ( st ); i++ ) {
printf ( "%d", p );
p = abs ( p – 1 );
}“`
只是这里还要考虑99变成100、999变成1000的情况,即位数变化。

也就是要判断last是不是9。

如果last不是9,那么上面的代码就可以完成任务,如果last是9,那么last之前那一位(即pos-2)就要加1,而last开始变成0101循环。
“`if ( last == ‘9’ ) {
for ( int i = 0; i < pos – 2; i++ ) {
printf ( "%c", st[i] );
}

<pre><code>printf ( "%c", st[pos – 2] + 1 );
int p = 0;

for ( int i = pos – 1; i < strlen ( st ); i++ ) {
printf ( "%d", p );
p = abs ( p – 1 );
}

break;
</code></pre>

} else {

<pre><code>for ( int i = 0; i < pos – 1; i++ ) {
printf ( "%c", st[i] );
}

int d;
sscanf ( ( st + pos – 1 ), "%d", &d );
printf ( "%d", d + 1 );
int p = 0;

for ( int i = pos + 1; i < strlen ( st ); i++ ) {
printf ( "%d", p );
p = abs ( p – 1 );
}

break;
</code></pre>

}“`
写到pos-2的时候,要多一个心眼,那就是pos正好是最开头的两个数字怎么办?比如,11和99。

如果是11,pos是1,pos-1是0,由于for循环的循环条件是先验的,所以int i=0之后,i<0不成立,循环不执行,然后scanf()把11变成了整数11,加1输出12。

如果是99,似乎遇到了点麻烦,pos是1,pos-2是-1,for循环是不做了,却会遇到st[-1]这样的情况,下标越界了。
不妨加一个判断。

if ( pos - 2 >= 0 ) {
    printf ( "%c", st[pos - 2] + 1 );

} else {
    printf ( '1' );
}

然而

printf ( "%c", st[pos - 2] + 1 )

等语句就会产生上面所说的情况三,进位以后产生了新的重复数。

不论是pos==strlen还是last==current,都会产生新的重复数。

有没有可能避免掉这种情况?

比如,加2?

如果last比current大1,那么加1以后,就一定会有重复的数字,比如43,4比3大1,加1以后变成44就是重复的,因此加2。

不过,加2,似乎也没有办法解决掉所有的问题,比如,2199,加2,变成2201,显然也不满足要求。

如果last比current大1,并且last非9的时候,加2,是可以解决问题的。

一旦last和current是98,加1变成99,不行,加2变成100,既要处理进位,还可能使得进位后的数字与前面形成新的重复数,不行。

那判断是98的时候,加3行不行呢?加3仅仅处理掉了当前这个是不重复的,却不能保证进位以后还是不重复。比如2198,加1不行,加2不行,加3变成2201,保证了01不再重复,却使得22重复了。

于是,判断到98,还要去处理last前面的两位,也就是pos-3和pos-2,要判断st[pos-3]是不是比st[pos-2]大1。

万一98就是最前面的呢?万一这个数字就是98呢?

如果真的这样考虑下去,一定能做,分类总可以把所有的可能考虑完整。

但是,太麻烦了。

我们不想做麻烦的事。

因此,一种可能的操作方法是加一个循环,不断判断,直到没有重复数字为止。

这样一来,就不能在程序中直接输出了,而是要先把结果输出到一个ans的字符串中,判断ans没有问题,再输出。

于是,把上面所有的printf()改为输出到ans中。

个位数就不需要ans了,直接输出结果吧。

其他情况,就要首先有一个ans。

char ans[1000] = {0};

定义一个ans字符数组,初始化为0,这是为了方便后面用strlen判断应该输出到ans的哪一位。

输出部分用到了sprintf()。

sprintf ( char*, const char*, ... );

第一个参数,是输出到的字符串。

 

第二个参数,是格式控制符。

第三个参数开始,就是各种各样的变量。

举几个例子。

有一个char数组ans。

sprintf ( ans, "%d", 123 );

ans数组就是’1’、’2’、’3’。

sprintf ( ans, "%f", -1.23 );

ans数组就是’-‘、’1’、’.’、’2’、’3’。

为了方便书写和阅读,下面的例子就会写成ans=“123”、ans=“-1.23”。

sprintf ( ans, "%.5f", -1.23 );

ans=“-1.23000”

甚至可以直接变成16进制。

sprintf ( ans, "%d=%x", 123 + 456, 123 + 456 );

123+456是579,第1个579会以%d的形式输出到ans中,然后输出中间的等号,第2个579会以%x的形式输出到ans中。

得到的结果应该是“579=243”。

#include <stdio.h>

int main() {
    char ans[100] = {0};
    sprintf ( ans, "%d=%x", 123 + 456, 123 + 456 );
    printf ( "%s\n", ans );
    return 0;
}

输出的结果是:

sp170206_171116

检验一下,确实如此:

sp170206_171135

更强大的功能暂时不说,但是就看上面几个例子,也能写出后面的代码了。

我们要把结果输出到ans中,那么就是ans。为了不让每次都从第0位开始覆盖,而是要不断往后写,这里就要指定ans开始的位置,需要开始写入的第一个位置恰好就是strlen(ans),这也就是之前要求把ans初始化为全0的原因,全部都是字符串结束符,就简化了操作。

因此,第一个参数,我们写( ans + strlen ( ans ) )。

sprintf ( ( ans + strlen ( ans ) ), "%c", st[i] );

把st的第i位,以%c的格式输出到ans的第strlen(ans)位,一开始strlen(ans)是0,正好就是ans开头,之后strlen(ans)变成1……

if ( pos - 2 >= 0 ) {
    sprintf ( ( ans + strlen ( ans ) ), "%c", st[pos - 2] + 1 );

} else {
    sprintf ( ( ans + strlen ( ans ) ), "%c", '1' );
}

这里的操作也是类似的,输出到ans的strlen(ans)位。

sprintf ( ( ans + strlen ( ans ) ), "%d", p );

这里输出的是整数,因此用的是%d,还是输出到ans的strlen(ans)位。

后面的操作类似,把所有的printf改成sprintf,输出到ans的第strlen位。

之后

if ( isTarget ( ans ) ) {
    printf ( "%s", ans );

} else {
    strcpy ( st, ans );
    /** Again **/
}

因此,上面的代码可以继续嵌套在一个while循环里面,循环的终止条件是ans中没有重复数。

可是这样一来,进入while的时候可没有ans,而循环体显然至少执行一次,所以可以把while循环改成do…while循环。

do {
    if ( strlen ( st ) == 1 ) {
    } else {
        while ( pos < strlen ( st ) ) {
            if ( last == current ) {
                if ( last == '9' ) {
                } else {
                }
            } else {
            }
            if ( pos == strlen ( st ) ) {
            }
        }
    }
} while ( !isTarget ( ans ) );

isTarget()也很好写。

int isTarget ( char* ans ) {

    for ( int i=1;i<strlen(ans);i++ ) {
        if ( ans[i] == ans[i - 1] ) {
           return 0;
        }
    }

    return 1;
}

退出do…while循环的时候,输出ans。

再调整一下变量的初始化,比如把ans的定义拿到最外面,等等。

除了第1次进入do..while,之后每次进入do…while都需要把ans复制给st,并且清空ans。

(清空很重要,否则下一轮循环就没法用strlen(ans)判断输出到第几位了)

if ( strlen ( ans ) ) {
    strcpy ( st, ans );

    for ( int i = 0; i < strlen ( ans ); i++ ) {
        ans[i] = 0;
    }
}```
补上多组输入输出。

补上换行符。

写换行符的时候,是这样处理的。

个位数依旧输出
<pre class="lang:c decode:true ">printf ( "%d", st[0] - '0' + 1 );</pre>
不加换行符。

退出do...while循环,依旧输出
<pre class="lang:c decode:true ">printf ( "%s", ans );</pre>
不加换行符。

这样一来,即便是个位数,退出do...while()循环,ans是空,不影响输出,之后再单独加上换行符。

当然,调整一下把个位数拿到do...while循环外面也是可以的。

试几组数据,发现100、1000出现问题了。

原因是00的重复,用%d变成了0,输出变成了1。因此,sprintf()那里,还不能只写%d,要写%02d。
<pre class="lang:c decode:true ">sprintf ( ( ans + strlen ( ans ) ), "%02d", d + 1 );</pre>
注意
<pre class="lang:c decode:true ">sprintf ( ( ans + strlen ( ans ) ), "%d", p );</pre>
不需要改动。

那
<pre class="lang:c decode:true ">sscanf ( ( st + pos - 2 ), "%d", &amp;d );</pre>
有需要改成%02d吗?

也是有必要的。

比如,445,只要44,不需要445。

所以读入的时候,不是吧st+pos-2这个字符串当做整数读入,而是只读后面2位且把那2位当做整数。

全部改完之后,提交,AC。

但是,整个程序还可以进一步优化。

先给出至此为止的代码,后文进一步优化。

int isTarget ( char* ans ) {
for ( int i = 1; i < strlen ( ans ); i++ ) {
if ( ans[i] == ans[i – 1] ) {
return 0;
}
}
return 1;
}

int main () {
int cas;
scanf ( “%d”, &cas );
for ( int t = 0; t < cas; t++ ) {
printf ( “case #%d:\n”, t );
char st[1000] = {0};
scanf ( “%s”, st );
char ans[1000] = {0};
do {
if ( strlen ( ans ) ) {
strcpy ( st, ans );
for ( int i = 0; i < strlen ( ans ); i++ ) {
ans[i] = 0;
}
}
if ( strlen ( st ) == 1 ) {
printf ( “%d”, st[0] – ‘0’ + 1 );
} else {
int pos = 1;
char last, current;
while ( pos < strlen ( st ) ) {
last = st[pos – 1];
current = st[pos];
if ( last == current ) {
if ( last == ‘9’ ) {
for ( int i = 0; i < pos – 2; i++ ) {
sprintf ( ( ans + strlen ( ans ) ), “%c”, st[i] );
}
if ( pos – 2 >= 0 ) {
sprintf ( ( ans + strlen ( ans ) ), “%c”, st[pos – 2] + 1 );
} else {
sprintf ( ( ans + strlen ( ans ) ), “%c”, ‘1’ );
}
int p = 0;
for ( int i = pos – 1; i < strlen ( st ); i++ ) {
sprintf ( ( ans + strlen ( ans ) ), “%d”, p );
p = abs ( p – 1 );
}
break;
} else {
for ( int i = 0; i < pos – 1; i++ ) {
sprintf ( ( ans + strlen ( ans ) ), “%c”, st[i] );
}
int d;
sscanf ( ( st + pos – 1 ), “%02d”, &d );
sprintf ( ( ans + strlen ( ans ) ), “%02d”, d + 1 );
int p = 0;
for ( int i = pos + 1; i < strlen ( st ); i++ ) {
sprintf ( ( ans + strlen ( ans ) ), “%d”, p );
p = abs ( p – 1 );
}
break;
}
} else {
pos++;
}
if ( pos == strlen ( st ) ) {
for ( int i = 0; i < pos – 2; i++ ) {
sprintf ( ( ans + strlen ( ans ) ), “%c”, st[i] );
}
int d;
sscanf ( ( st + pos – 2 ), “%02d”, &d );
sprintf ( ( ans + strlen ( ans ) ), “%02d”, d + 1 );
}
}
}
} while ( !isTarget ( ans ) );
printf ( “%s”, ans );
printf ( “\n” );
}
return 0;
}
“`
优化,首先从消除代码复制开始。

我们看到循环输出0和1那部分,几乎是一模一样的代码。

因此,我们可以把它们提取出来,做一个printZeroAndOne()函数,函数接受的参数是begin和end的位数,或者也可以是输出多少位。

同样地,照抄pos之前的数字,也可以提取出来。

做一个printTheSame()。
“`void printTheSame ( int cnt, char* st, char * ans ) {
for ( int i = 0; i < cnt; i++ ) {
sprintf ( ( ans + strlen ( ans ) ), “%c”, st[i] );
}
}

void printZeroAndOne ( int cnt, char* ans ) {

int p = 0;

for ( int i = 0; i < cnt; i++ ) {
    sprintf ( ( ans + strlen ( ans ) ), "%d", p );
    p = abs ( p - 1 );
}

}“`
中间进位的部分,各不相同,也没法做成一个函数。

到这里,整个程序已经很好了。

至此,整个程序已经很好了。

“代码复制”这一个大忌解决掉,剩下的不进行优化,问题也不大。

如果有兴趣,也可以进一步尝试优化。

至此,完整代码为:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void printTheSame ( int cnt, char* st, char * ans ) {
    for ( int i = 0; i < cnt; i++ ) {
        sprintf ( ( ans + strlen ( ans ) ), "%c", st[i] );
    }
}

void printZeroAndOne ( int cnt, char* ans ) {
    int p = 0;
    for ( int i = 0; i < cnt; i++ ) {
        sprintf ( ( ans + strlen ( ans ) ), "%d", p );
        p = abs ( p - 1 );
    }
}

int isTarget ( char* ans ) {
    for ( int i = 1; i < strlen ( ans ); i++ ) {
        if ( ans[i] == ans[i - 1] ) {
            return 0;
        }
    }
    return 1;
}

int main () {
    int cas;
    scanf ( "%d", &cas );
    for ( int t = 0; t < cas; t++ ) {
        printf ( "case #%d:\n", t );
        char st[1000] = {0};
        scanf ( "%s", st );
        char ans[1000] = {0};
        do {
            if ( strlen ( ans ) ) {
                strcpy ( st, ans );
                for ( int i = 0; i < strlen ( ans ); i++ ) {
                    ans[i] = 0;
                }
            }
            if ( strlen ( st ) == 1 ) {
                printf ( "%d", st[0] - '0' + 1 );
            } else {
                int pos = 1;
                char last, current;
                while ( pos < strlen ( st ) ) {
                    last = st[pos - 1];
                    current = st[pos];
                    if ( last == current ) {
                        if ( last == '9' ) {
                            printTheSame ( pos - 2, st, ans );
                            if ( pos - 2 >= 0 ) {
                                sprintf ( ( ans + strlen ( ans ) ), "%c", st[pos - 2] + 1 );
                            } else {
                                sprintf ( ( ans + strlen ( ans ) ), "%c", '1' );
                            }
                            printZeroAndOne ( strlen ( st ) - pos + 1, ans );
                            break;
                        } else {
                            printTheSame ( pos - 1, st, ans );
                            int d;
                            sscanf ( ( st + pos - 1 ), "%02d", &d );
                            sprintf ( ( ans + strlen ( ans ) ), "%02d", d + 1 );
                            printZeroAndOne ( strlen ( st ) - pos - 1, ans );
                            break;
                        }
                    } else {
                        pos++;
                    }
                    if ( pos == strlen ( st ) ) {
                        printTheSame ( pos - 2, st, ans );
                        int d;
                        sscanf ( ( st + pos - 2 ), "%02d", &d );
                        sprintf ( ( ans + strlen ( ans ) ), "%02d", d + 1 );
                    }
                }
            }
        } while ( !isTarget ( ans ) );
        printf ( "%s", ans );
        printf ( "\n" );
    }
    return 0;
}

2017-02-06_17-21一稿

2017-02-09_17-29二稿

0 条回应