3.14学习总结
目录
3.14学习总结
做了几道算法题
水题，使用深搜轻易求解
#include <stdio.h>
#include <stdlib.h>
int n,num=0;
int a[15],b[10086][15];
//深搜
int hly(int s,int i)
{
if(i==11){
if(s==n)
{
//将每种配料所放的质量储存到数组b中
for(int i=1;i<=10;i++){
b[num][i]=a[i];
}
num++;
}
return;
}
for(int j=1;j<=3;j++){
a[i]+=j;
hly(s+j,i+1);
a[i]-=j;
}
return;
}
int main()
{
scanf("%d",&n);
//由题可知，烤鸡的美味程度只能在10到30之间
if(n>=10&&n<=30)
hly(0,1);
//输出方案总数
printf("%d\n",num);
//输出每种配料所放的质量
for(int i=0;i<num;i++){
for(int j=1;j<=10;j++){
printf("%d ",b[i][j]);
}
printf("\n");
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
int a,b,c;
int A,B,C;
int flog=0;
int book[10],d[10];
//将九个数字任意排序，s表示确定第s位数，深搜
int hly(int s)
{
if(s==10)
{
//每三个数为一组，用ABC表示
A=d[1]*100+d[2]*10+d[3];
B=d[4]*100+d[5]*10+d[6];
C=d[7]*100+d[8]*10+d[9];
//检测是否满足条件
if(A*b==B*a&&A*c==C*a)
{
printf("%d %d %d\n",A,B,C);
flog=1;
}
}
for(int i=1;i<=9;i++)
{
//若i没有被使用
if(book[i]==0)
{
d[s]+=i;
book[i]=1;
hly(s+1);
d[s]-=i;
book[i]=0;
}
}
}
int main()
{
scanf("%d %d %d",&a,&b,&c);
hly(1);
if(flog==0)
printf("No!!!\n");
return 0;
}
这道题跟全排列类似，但是又有一点不同，选出了这r个数后，不分每个数的排列顺序，所以不能直接使用全排列的思想，还有场宽这个词之前没听过，刚开始以为直接在数前面加两个空格，然后挂了，后面才发现不是这样，场宽是指数据项的宽度，可以用printf（”%kd“，n）；来输出场宽为k的数字n。
#include <stdio.h>
#include <stdlib.h>
int n,m;
int a[25];
//用深搜确定第s个数字
int hly(int s)
{
//全部选择完了
if(s==m+1)
{
for(int i=1;i<=m;i++)
{
//场宽为3
printf("%3d",a[i]);
}
printf("\n");
return;
}
for(int i=a[s-1]+1;i<=n;i++)
{
//从小到大寻找第s个数的值
a[s]=i;
//寻找第s+1个数；
hly(s+1);
}
return;
}
int main()
{
scanf("%d %d",&n,&m);
hly(1);
return 0;
}
水题，挺简单的，刚开始一直做不出来，以为是算法问题，后面才发现我int了一个字符串数组……，粗心大意，以后得注意细节
#include <stdio.h>
#include <stdlib.h>
char a[55][55];
int main()
{
int n,m,i,j,x,y,min=2e9,num;
scanf("%d %d\n",&n,&m);
for(i=1;i<=n;i++){
scanf(" %s",a[i]);
}
//对每种颜色的行数进行枚举
for(i=1;i<=n-2;i++){
for(j=1;j<=n-i-1;j++){
//每次循环将涂格子数清零
num=0;
//涂白色格子
for(x=1;x<=i;x++){
for(y=0;y<m;y++){
if(a[x][y]!='W')
num++;
}
}
//涂蓝色格子
for(x=i+1;x<=i+j;x++){
for(y=0;y<m;y++){
if(a[x][y]!='B')
num++;
}
}
//涂红色格子
for(x=i+j+1;x<=n;x++){
for(y=0;y<m;y++){
if(a[x][y]!='R')
num++;
}
}
//寻找最小的涂格子数
if(min>num)
min=num;
}
}
printf("%d",min);
return 0;
}
寻找第一个成员站的位置，看能不能站下站完k名成员，特殊情况，k小于0时，站法零种，k=1时重复计算了，方法数要除以2。
#include <stdio.h>
#include <stdlib.h>
char a[205][205];
int main()
{
int n,m,l,s=0,flag;
scanf("%d %d %d",&n,&m,&l);
//初始化地图
for(int i=1;i<=n;i++)
scanf(" %s",a[i]);
//特例，没有队员，站不了
if(l<=0)
{
printf("0\n");
return;
}
//寻找第一位队员站的位置
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
if(a[i][j]=='.'){
flag=0;
//往右寻找能不能站完
for(int k=0;k<=l-1;k++){
if(a[i][j+k]!='.')
flag=1;
}
if(flag==0)
s++;
flag=0;
//向下寻找能不能站完
for(int k=0;k<=l-1;k++){
if(a[i+k][j]!='.')
flag=1;
}
if(flag==0)
s++;
}
}
}
//特列，重复计算了，方法除以2；
if(l==1)
s/=2;
printf("%d\n",s);
return 0;
}
啊哈算法中讲枚举时所用的例题
#include <stdio.h>
#include <stdlib.h>
//确实每个数用的火柴棍数量
int a[10]={6,2,5,5,4,5,6,3,7,6};
int hly(int x)
{
int s=0;
//根据x位数不同，确定x所用的火柴棍数量
while(x>9){
s+=a[x%10];
x/=10;
}
s+=a[x];
return s;
}
int main()
{
int n,num=0;
scanf("%d",&n);
//枚举A与B的值
for(int i=0;i<=1111;i++){
for(int j=0;j<=1111;j++){
int k=i+j;
//判断是否满足条件
if(hly(i)+hly(j)+hly(k)==n-4){
num++;
}
}
}
printf("%d\n",num);
return 0;
}