8598 整除15 问题
时间限制:300MS 内存限制:1000K 提交次数:0 通过次数:0
语言: not limited
描述
问题描述：
给定一个只包含数字[0..9]的字符串，求使用字符串中的某些字符，构建一个能够整除15的最大的整数。
注意，字符串中的每个字符只能使用一次。
编程任务：
求由给定字符串构建的能够整除15的最大整数。
输入格式
输入数据为一个只包含数字[0..9]字符串，字符串的长度为1~1000。
输出格式
将构建出的最大整数输出。
如果无法构建出能够整除15的整数，请输出
“impossible”
输入样例
02041
输出样例
4200
Hint
从原来的字串中选择出最少最小的数扣除以满足整除3和5的要求。
28
把0~9数分为如下几类：
0，3，6 ，9：这四种数不影响
2，5，8：除3余2
1，4，7：除3余1
这个题目，考虑能否满足整除5的情况，这比较简单，不详述。只要能满足整除5，进行如下步骤：
然后再考虑从原字串中删除最少而且最小的数使得满足整除3。
有以下几种情况：
情况一：
这个数上各位数字和除3余0。不用删除操作。
情况二：
给定的数上各位数字和除3余1。那么只要删除余1的那一类数中最小的一个。如果没有数串中没有余1的数，就删除两个余2的数。
情况三：
给定的数上各位数字和除3余2。那么只要删除余1的那一类数中最小的两个。如果没有数串中没有余1的数，就删除一个最小的余2的数。
最后，剩余的数串以最大的并且以满足整除5的要求输出。在0存在的时候，就按计数的顺序输出即可。如果在数串中没有0，则必须有个5放在个位。
-----------------------------------------------------------------
8598整除15问题（贪心）
#include<stdio.h>
#include"malloc.h"
#include"string.h"
int delet(int *b,int del_1,int del_2,int n)
{
int max,min,i,j;
if(del_2!=-1){
if(del_1<del_2) {min=del_1;max=del_2;}
else {min=del_2;max=del_1;}
for(i=max;i<n-1;i++)
{
b[i]=b[i+1];
}
for(i=min;i<n-2;i++)
{
b[i]=b[i+1];
}
}
else
for(i=del_1;i<n-1;i++)
{
b[i]=b[i+1];
}
return 0;
}
int sort(int *b,int m,int five,int zero)
{
int i,j,temp,n;
n=m;
if(zero==-1)
{temp=b[n-1]; b[n-1]=b[five]; b[five]=temp;n=n-1; }
for(i=0;i<n;i++)
for(j=i;j<n;j++)
{
if(b[i]<b[j]) {temp=b[i]; b[i]=b[j]; b[j]=temp; }
}
return 0 ;
}
int main()
{
char a[1000];
int i,n,sum=0;
int *b,del_1=-1,del_2=-1;
int low2_1=-1,low2_2=-1,low1_1=-1,low1_2=-1,five=-1,zero=-1,remainder,count5=0;
scanf("%s",&a);
n=strlen(a);
b=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
b[i]=a[i]-48;
}
for(i=n-1;i>=0;i--){
sum=b[i]+sum;
if((zero==-1)&&(b[i]==0)) zero=i;
if((five==-1)&&(b[i]==5)) five=i;
if((b[i]==5))count5++;
if(b[i]%3==1)
{
if((low1_1==-1)&&(low1_2==-1))
low1_1=i;
else if((low1_1!=-1)&&(low1_2==-1))
low1_2=i;
else if(!((b[low1_1]==1)&&(b[low1_2]==1)))
{
if(b[i]<b[low1_1]) low1_1=i;
else if(b[i]<b[low1_2]) low1_2=i;
}
}
if(b[i]%3==2)
{
if((low2_1==-1)&&(low2_2==-1))
low2_1=i;
else if((low2_1!=-1)&&(low2_2==-1))
low2_2=i;
else if(!((b[low2_1]==2)&&(b[low2_2]==2)))
{
if(b[i]<b[low2_1]) low2_1=i;
else if(b[i]<b[low2_2]) low2_2=i;
}
}
}
remainder=sum%3;
if((zero==-1)&&(five==-1))
printf("impossible");
else
{
if(remainder==0)
{
sort(b,n,five,zero);
for(i=0;i<n;i++)
printf("%d",b[i]);
}
else{
if(remainder==1)
{
if((low1_1!=-1)&&(low1_2==-1))
del_1=low1_1;
else if((low1_1!=-1)&&(low1_2!=-1))
{if(b[low1_1]<=low1_2) del_1=low1_1;}
else
{
del_1=low2_1;del_2=low2_2;
}
}
if(remainder==2)
{
if((low2_1!=-1)&&(low2_2!=-1))
{
if((b[low2_1]==5)&&(b[low2_2]>b[low2_1]))
del_1=low2_2;
else if((b[low2_2]==5)&&(b[low2_1]>b[low2_2]))
del_1=low2_1;
else
{if(b[low2_1]<=b[low2_2]) del_1=low2_1;
else del_1=low2_2;
}
}
else if((low2_1!=-1)&&(low2_2==-1)&&(b[low2_1]!=5))
del_1=low2_1;
else
{del_1=low1_1;del_2=low1_2;}
}
delet(b,del_1,del_2,n);
if(del_2==-1)
{
if((n-1<2)&&(b[0]!=0))
printf("impossible");
else
{sort(b,n-1,five,zero);
for(i=0;i<n-1;i++)
printf("%d",b[i]);}
}
else
{
if((n-2<2)&&(b[0]!=0))
printf("impossible");
else
{
sort(b,n-2,five,zero);
for(i=0;i<n-2;i++)
printf("%d",b[i]);
}
}
}
}
return 0;
}
分享到：
相关推荐
给定一个只包含数字 [0..9] 的字符串，求使用字符串中的某些字符，构造一个能够被15整除的最大整数。注意，字符串中的每个字符最多只能使用一次。 输入：程序从标准输入读入数据，每行数据由一串数字组成，长度为1到...
给定一个只包含数字[0..9]的字符串，求使用字符串中的某些字符，构建一个能够整除15的最大的整数。 注意，字符串中的每个字符只能使用一次。 编程任务： 求由给定字符串构建的能够整除15的最大整数。 输入格式 ...
总的来说，解决“整除15问题”的算法涉及到了字符串处理、整数除法、数的分解以及搜索策略等多方面知识。通过合理地组织代码和运用这些概念，我们可以编写出一个高效的解决方案来处理此类问题。
根据题目要求，本文将对“整除15问题/贪心算法/C++”这一主题进行深入探讨，并结合题目描述及部分代码示例，提炼出关键的知识点与算法思路。 ### 整除15问题背景 #### 问题描述 题目要求我们处理一个由数字0到9...
整除15问题的算法设计 在计算机科学和算法研究中，整除15问题是一个有趣的编程挑战。它要求开发者构建一个能够整除15的最大的整数，前提是这个整数的数字必须来源于一个给定的数字字符串。这类问题通常需要综合考虑...
在编程领域，整除15的问题是一个常见的数学与算法题目，它涉及到整数的除法、余数计算以及条件判断等基本概念。本主题主要探讨如何利用C语言来解决这类问题，同时也涉及到了算法的设计与分析，这对于提升编程技能和...
给定一个只包含数字[0..9]的字符串，求使用字符串中的某些字符，构建一个能够整除15的最大的整数。 注意，字符串中的每个字符只能使用一次。 编程任务： 求由给定字符串构建的能够整除15的最大整数。
判断能否被15整除的问题，注意特殊情况那个的判断和输出
给定一个只包含数字[0..9]的字符串，请使用字符串中的某些字符，构建一个能够整除 15最大的整数。注意，字符串中的每个字符只能使用一次。 由文件input.txt给出输入数据。输入数据为一个只包含数字[0..9]字符串，...
例如，15可以被3整除，因为15 ÷ 3 = 5，没有余数。而15不能被4整除，因为15 ÷ 4 = 3...3，有余数。 接下来，我们将用编程语言（如Python）来实现这个功能。程序通常会从用户那里获取输入，这可以通过`input()`...
例如，15可以被3和5整除，但不能被7整除。 接下来，我们来看如何用C#实现这个功能。有几种不同的方法可以实现这个需求，包括使用`if`语句和`switch`语句。这里我们主要讨论`if`语句的实现，因为`switch`语句在处理...
标签“整除”进一步强调了这个问题的核心——对整数进行除法运算和检查可除性。在上述代码示例中，我们不仅展示了如何检查单个数，还展示了如何处理一组数，这在处理数据集合时非常常见。 在提供的压缩包文件“整除...
在这个问题中，我们将使用循环（如for或while）来遍历从1到k的所有自然数，以及条件语句（if）来检查每个数是否能被13或17整除。 程序设计的步骤可能如下： 1. **定义变量**：声明一个变量`k`用于存储用户输入的...
例如，12和15的最大公约数是3，因为3是12和15的最大公约数。 10. 数的奇偶性：一个数可以是奇数或偶数。如果一个数的最后一位是0、2、4、6、8，那么这个数是偶数；否则，它是奇数。 11. 数的和：两个或多个数的...
该问题要求使用给定的数字字符串，构建一个能够整除15的最大整数，注意每个字符只能使用一次。下面是对该问题的详细解析和解决方案。 问题描述： 给定一个只包含数字[0…9]的字符串，请使用字符中的某些字符，构建...
- **例1**：寻找七位数2345能被15整除的条件，即这个数能同时被3和5整除。由整除特征可知，末尾必须为0或5，而前两位数字之和2+3+A+B能被3整除。所以A+B可以是1、4、7或10。 - **例2**：构造能被2、5、5整除的三位数...
这是我自己写的使用C语言实现被5整除数的程序，程序可能不是最优的，但是希望能对对学习C语言程序设计的入门学生有帮助。
计算并输出n(包括n)以内能被3或5整除的所有自然数之和的简单C++程序
C语言程序设计-编写函数判断一个整数能否同时被3和5整除，若能则返回值为1，否则为0;调用该函数求出15~300之间能同时被3和5整除的数的个数;.c