持续xxx定律, 改了许久还是WA
继续xxx定律, 改了许久还是WA
http://acm.hdu.edu.cn/showproblem.php?pid=3784
题目内容:
Problem Description
当n为3时,我们在验证xxx定律的过程中会得到一个序列,3,5,8,4,2,1,将3称为关键数,5,8,4,2称为覆盖数。现在输入n个数字a[i],根据关键数与覆盖数的理论,我们只需要验证其中部分数就可以确定所有数满足xxx定律,输出输入的n个数中的关键数。如果其中有多个关键数的话按照其输入顺序的逆序输出。
Input
输入数据包含多个用例,每个用例首先包含一个整数n,然后接下来一行有n个整数a[i],其中:
1<=n<=500
1<a[i]<=1000
Output
请计算并输出数组a中包含的关键数,并按照其输入顺序的逆序输出,每个用例输出占一行。
Sample Input
3
3 8 4
5
3 8 4 7 15
5
3 8 4 15 7
0
Sample Output
3
15 7 3
7 15 3
注XXX定律是:对于一个数n,如果是偶数,就把n砍掉一半;如果是奇数,把n变成 3*n+ 1后砍掉一半,直到该数变为1为止。
我的基本思想是:
两个数组:flag和stack。
flag用来标记输入的数字串标记表示关键数。
stack用来存储输入的数字串。
然后下面依次扫描stack里面的并且用xxx定律去验证,每验证到一个满足条件的,就把flag取消,表示是覆盖数。
上代码:
修改了一段时间,还是没有发现问题。
麻烦各位帮帮忙啦~
------解决方案--------------------
以下一行:
printf("\b\n");
不能产生满足题目要求的效果. 如下修改AC:
http://acm.hdu.edu.cn/showproblem.php?pid=3784
题目内容:
Problem Description
当n为3时,我们在验证xxx定律的过程中会得到一个序列,3,5,8,4,2,1,将3称为关键数,5,8,4,2称为覆盖数。现在输入n个数字a[i],根据关键数与覆盖数的理论,我们只需要验证其中部分数就可以确定所有数满足xxx定律,输出输入的n个数中的关键数。如果其中有多个关键数的话按照其输入顺序的逆序输出。
Input
输入数据包含多个用例,每个用例首先包含一个整数n,然后接下来一行有n个整数a[i],其中:
1<=n<=500
1<a[i]<=1000
Output
请计算并输出数组a中包含的关键数,并按照其输入顺序的逆序输出,每个用例输出占一行。
Sample Input
3
3 8 4
5
3 8 4 7 15
5
3 8 4 15 7
0
Sample Output
3
15 7 3
7 15 3
注XXX定律是:对于一个数n,如果是偶数,就把n砍掉一半;如果是奇数,把n变成 3*n+ 1后砍掉一半,直到该数变为1为止。
我的基本思想是:
两个数组:flag和stack。
flag用来标记输入的数字串标记表示关键数。
stack用来存储输入的数字串。
然后下面依次扫描stack里面的并且用xxx定律去验证,每验证到一个满足条件的,就把flag取消,表示是覆盖数。
上代码:
//http://acm.hdu.edu.cn/showproblem.php?pid=3784
#include<stdio.h>
int flag[1003];//防止取消掉一些数字之后,无法对每个数字进行判定
//int flag_tojudge[1003];
int stack[503];
int main()
{
int n,i;
//freopen("test.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d", &n ) && n != 0)
{
for(i=0 ;i< 1003 ;i++)
{
flag[i]=0;
// flag_tojudge[i] = 0;
}
for(i=0 ;i< n;i++)
{
scanf("%d",&stack[i]);
flag[stack[i]] = 1;
// flag_tojudge[stack[i]] = 1;
}
for(i=0 ;i<n ;i++)//对每个输入数字进行判断
{
int temp = stack[i];
while( temp != 1)
{
if( temp %2 == 0)
{
temp = temp/2;
if( temp <= 1000 && temp !=1)
flag[temp] = 0;
}
else
{
temp = (temp*3+1)/2;
if( temp <= 1000 && temp != 1)
flag[temp]= 0;
}
}
}
for(i= n-1 ;i>=0 ;i--)
{
if( flag[stack[i]] == 1)
{
printf("%d ",stack[i]);
}
}
printf("\b\n");
}
return 0;
}
修改了一段时间,还是没有发现问题。
麻烦各位帮帮忙啦~
------解决方案--------------------
以下一行:
printf("\b\n");
不能产生满足题目要求的效果. 如下修改AC:
//http://acm.hdu.edu.cn/showproblem.php?pid=3784
#include<stdio.h>
int flag[1003];//防止取消掉一些数字之后,无法对每个数字进行判定
//int flag_tojudge[1003];
int stack[503];
int main()
{
int n,i;
//freopen("test.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d", &n ) && n != 0)
{
int temp; //加
for(i=0 ;i< 1003 ;i++)
{
flag[i]=0;
// flag_tojudge[i] = 0;
}
for(i=0 ;i< n;i++)
{
scanf("%d",&stack[i]);
flag[stack[i]] = 1;
// flag_tojudge[stack[i]] = 1;
}
for(i=0 ;i<n ;i++)//对每个输入数字进行判断
{
temp = stack[i]; //改 int temp = stack[i];
if (!flag[temp]) continue; //加
while( temp != 1)
{
if( temp %2 == 0)
{
temp = temp/2;
if( temp <= 1000 && temp !=1)
flag[temp] = 0;
}
else
{
temp = (temp*3+1)/2;
if( temp <= 1000 && temp != 1)
flag[temp]= 0;
}
}
}
temp = 1;//加
for(i= n-1 ;i>=0 ;i--)
{
if( flag[stack[i]] == 1)
{
if (temp)//加
{
printf("%d",stack[i]);