基础练习 十六进制转八进制

问题描述
  给定n个十六进制正整数,输出它们对应的八进制数。

输入格式
  输入的第一行为一个正整数n (1<=n<=10)。
  接下来n行,每行一个由0~9、大写字母A~F组成的字符串,表示要转换的十六进制正整数,每个十六进制数长度不超过100000。

输出格式
  输出n行,每行为输入对应的八进制正整数。

  【注意
  输入的十六进制数不会有前导0,比如012A。
  输出的八进制数也不能有前导0。

样例输入
  2
  39
  123ABC

样例输出
  71
  4435274

  提示
  先将十六进制数转换成某进制数,再由某进制数转换成八进制。

本来打算先将十六进制转换成十进制数,再由十进制数转换成八进制,试了多次发现行不通(数字太大超过 unsigned long long范围),十六进制转换成十进制数,再由十进制数转换成八进制代码如下:

#include<stdio.h>
#include<math.h>
#include<string.h>
int main()
{
	int n,i,num,j;
	int temp,a[100];
	int count=1,num1=0;
	char str1[100000];
	unsigned long long sum=0;
	
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		sum=0,count=1,num1=0;
		scanf("\n");
		strcpy(str1," ");
		gets(str1);
		temp=strlen(str1);
		for(j=0;j<=strlen(str1);j++)
		{
				
			if(str1[j]>='A'&&str1[j]<='F')
			{
				str1[j]=str1[j]-'A'+10;
			}
			else if(str1[j]>='0'&&str1[j]<='9')
			{
				str1[j]=str1[j]-'0';
			}
			sum+=str1[j]*pow(16,temp-1);
			temp=temp-1;
		}
		j=0;
		while(sum)
		{
			a[j]=sum%8;
			sum=sum/8;
			j++;
		}
		for(j=j-1;j>=0;j--)
		{
			printf("%d",a[j]);
		}
	}
	return 0;	
} 

十六进制转换成二进制数,再由二进制数转换成八进制代码如下:

 

组合知识

 

从m个物品里选出n个的方案数,记作CnmCmn,即为组合数
组合数有很多很多的性质和定理。。。
注意由于本人沉迷玩梗无法自拔,如果看见您看不懂的梗请随意跳过。

组合数通项公式
Cnm=m!n!∗(m−n)!
Cmn=m!n!∗(m−n)!

证明:现在我们从m个不同的数里选出n个数组成一个排列,第一个位子上的数有m种取法,第二个位子上的有m-1种,第三个位子上有m-2种。。。共有m!(m−n)!m!(m−n)!种
然而,我们对于顺序没有要求,假设取出了n个数,第一个位子上有n种放法,第二个位子上有n-1种。。。所以我们刚才得到的哪个东西还要除一个n!n!
组合数递推公式
Cnm=Cnm−1+Cn−1m−1
Cmn=Cm−1n+Cm−1n−1

证明:从m个不同的数中取n个,第m个数如果取的话有Cn−1m−1Cm−1n−1种取法,如果不取则有Cnm−1Cm−1n种。
如果您是组合数新手,请牢记以上两个公式
性质1
Cnm=Cm−nm
Cmn=Cmm−n

证明:显然从m个物品里选n个和从m个物品里选m-n个丢掉的方案数是一样的。
性质2
Crm+r+1=∑i=0rCim+i
Cm+r+1r=∑i=0rCm+ii

证明:用组合数的递推公式。
首先C0m=C0m+1=1Cm0=Cm+10=1
C0m+C1m+1+C2m+2+…+Crm+rCm0+Cm+11+Cm+22+…+Cm+rr=
C1m+C1m+1+C2m+2+…+Crm+rCm1+Cm+11+Cm+22+…+Cm+rr=
C1m+2+C2m+2+…+Crm+rCm+21+Cm+22+…+Cm+rr=
Crm+r+1Cm+r+1r
性质3
Cnm∗Crn=Crm∗Cn−rm−r
Cmn∗Cnr=Cmr∗Cm−rn−r

证明:用组合数的通项公式
Cnm∗Crn=Cmn∗Cnr=
m!n!(m−n)!∗n!r!(n−r)!=m!n!(m−n)!∗n!r!(n−r)!=
m!r!(m−r)!∗(m−r)!(m−n)!(n−r)!=m!r!(m−r)!∗(m−r)!(m−n)!(n−r)!=
Crm∗Cn−rm−rCmr∗Cm−rn−r
性质4(二项式定理)
∑i=0mCim=2m
∑i=0mCmi=2m

证明:显然CimCmi代表一个m位二进制数有i个0的情况下的数量,那么这个和就是m位二进制数的数量了。
推广一下这个二项式定理:
∑i=0mCim∗xi=(x+1)m
∑i=0mCmi∗xi=(x+1)m

这个又怎么证明呢?先把(x+1)m(x+1)m写成(x+1)(x+1)(x+1)…(x+1)(x+1)(x+1)…的格式,然后每一项很精妙啊,比如说i次方项,选的ii个xx是从哪个括号里来呢?有CimCmi种方案吧,所以xixi项的系数是CimCmi。
这就是杨辉三角的应用(可以自行百度)
性质5
C0m−C1m+C2m−…±Cmm=0
Cm0−Cm1+Cm2−…±Cmm=0

证明:假如m是奇数的花,由性质1可知正确。
假如m是偶数的花,这个里面的花,用一下递推公式,然后显然C0m−1=C0m=1Cm−10=Cm0=1并且Cm−1m−1=Cmm=1Cm−1m−1=Cmm=1,则:
C0m−C1m+C2m−…+Cmm=Cm0−Cm1+Cm2−…+Cmm=
C0m−1−C0m−1−C1m−1+C1m−1+C2m−1−…+Cm−1m−1=0Cm−10−Cm−10−Cm−11+Cm−11+Cm−12−…+Cm−1m−1=0
性质6
C0m+C2m+C4m…=C1m+C3m+C5m+…=2m−1
Cm0+Cm2+Cm4…=Cm1+Cm3+Cm5+…=2m−1

证明:这个根据性质4和性质5可知正确。
性质7
Crm+n=C0m∗Crn+C1m∗Cr−1n+…+Crm∗C0n
Cm+nr=Cm0∗Cnr+Cm1∗Cnr−1+…+Cmr∗Cn0

证明:很简单,考虑我选出的r个物品在前m个物品有几个,在后n个物品里有几个即可。
特别的:
Cnm+n=C0m∗C0n+C1m∗C1n+…+Cmm∗Cmn
Cm+nn=Cm0∗Cn0+Cm1∗Cn1+…+Cmm∗Cnm

这个是根据性质1变形得到的。
性质8
n∗Cnm=m∗Cn−1m−1
n∗Cmn=m∗Cm−1n−1

证明:运用通项公式
n∗Cnm=n∗Cmn=
n∗m!n!(m−n)!=n∗m!n!(m−n)!=
m!(n−1)!(m−n)!=m!(n−1)!(m−n)!=
m∗(m−1)!(n−1)!(m−n)!=m∗Cn−1m−1m∗(m−1)!(n−1)!(m−n)!=m∗Cm−1n−1
性质9
∑i=1nCin∗i=n∗2n−1
∑i=1nCni∗i=n∗2n−1

证明:用通项公式
∑ni=1Cin∗i=n∗2n−1=∑i=1nCni∗i=n∗2n−1=
∑ni=1n!(i−1)!(n−i)!=∑i=1nn!(i−1)!(n−i)!=
(∑ni=1(n−1)!(i−1)!(n−i)!)∗n=(∑i=1n(n−1)!(i−1)!(n−i)!)∗n=
(∑n−1i=0Cin)∗n=(∑i=0n−1Cni)∗n=
现在看性质4。
n∗2n−1n∗2n−1
性质10
∑i=1nCin∗i2=n∗(n+1)∗2n−2
∑i=1nCni∗i2=n∗(n+1)∗2n−2

证明:
和上一个性质有些类似。
∑ni=1Cin∗i2=∑i=1nCni∗i2=
用和上面差不多的方法得到:
(∑n−1i=0Cin−1∗(i+1))∗n=(∑i=0n−1Cn−1i∗(i+1))∗n=
(∑n−1i=0Cin−1∗i+∑n−1i=0Cin−1)∗n=(∑i=0n−1Cn−1i∗i+∑i=0n−1Cn−1i)∗n=
用性质9和性质4可以得到:
(2n−2∗(n−1)+2n−1)∗n=(2n−2∗(n−1)+2n−1)∗n=
很明显2n−1=2∗2n−22n−1=2∗2n−2
所以原式=2n−2∗(n+1)∗n2n−2∗(n+1)∗n
性质11
∑i=0n(Cin)2=Cn2n
∑i=0n(Cni)2=C2nn

证明:boshi说,他的门前有两棵树,一棵是枣树,另一棵也是枣树,每棵树上有n个枣子,每个枣子都有一个不同的神奇的膜法符号。现在boshi从两棵树上一共打下了n个枣子,那么一共有多少种方案?是Cn2nC2nn,也是第一棵树上打下i个枣子,从第二棵树上打下(n-i)棵枣子的方案,根据乘法原理乘起来,又因为Cin=Cn−inCni=Cnn−i,所以得到上一个式子。
卢卡斯定理
简单的说就是求Cnm%pCmn%p的时候可以化作Cnm=Cn/pm/p∗Cn%pm%pCmn=Cm/pn/p∗Cm%pn%p,那么只要递归Cn/pm/pCm/pn/p即可。
证明我蠢我不会自己想

后记
啊啊啊搞了一下午终于证完了累死了。。。感觉自己和组合数的感情有了明显的提升(才怪)。。。
在文章的最后%一发数王。。。
%%%%%%%%%数王您太强了%%%%%%%%%%%
数王说以上所有定理都可以用那个那个那个证,虽然我不知道那个是哪个,但是反正好强啊%%%%%%%%
好吧以上都是不正经内容,正经内容是:
在做题的时候大家可能不一定都会遇到这些性质,但是在手动证明完这些性质后对于组合数变形的问题就会有更深一层的理解,总之,组合数性质可以用一下方法推出:
1.情景假设法(假设boshi从枣树选枣子的方案。。。)
2.隔板法(boshi把枣子放成一排,通过在枣子间添加隔板来分组。。。)
3.通向公式法
4.递推公式法

转载自https://blog.csdn.net/litble/article/details/75913032

暴力出奇迹

题目描述

给出多个整数n,要求求出a,b,c字典序最小的 a2+b2+c2=n

输入

一个整数t,表明数据组数 (t <= 10)
接下来t行,每行一个整数n (1 <= n <= 10000)

输出

三个整数 a,b,c
如果无解,输出”???”

样例输入

2
7
30

样例输出

???
1 2 5

来源/分类

2018新生赛 八

#include<cstdio>
int main()
{
	//freopen("in.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		int n,flag=0;
		scanf("%d",&n);
		int i=0,j=0,k=0;
		for(i=0;i*i+j*j+k*k<=n;i++){
			for(j=i;i*i+j*j+k*k<=n;j++){
				for(k=j;i*i+j*j+k*k<=n;k++){
					//printf("%d %d %d",i,j,k);
					if(i*i+j*j+k*k==n){
							flag=1;
							break;
					}
				}
				if(flag) break;
				k=j;//若不还原,则可能开始下一次循环时循环的判断条件提前为假 
			}
			if(flag) break;
			j=i;
		}
		if(flag) printf("%d %d %d\n",i,j,k);
		else printf("???\n");
	}
}

 

结构指针

结构指针的概念

结构指针就是指向结构变量的指针

例:

struct student s1={10,"wang",8,7,9},*p;

p=&s1;

第一条语句定义了struct student 类型的变量s1并初始化,另外还定义了一个结构指针变量

第二条语句使结构指针指向结构变量s1,结构指针的值实际上是结构变量的首地址

用*p访问结构成员
(*p).num=10;

(*p)的括号是不可少的,因为成员运算符“.”的优先级高于“*”的优先级。

用指向运算符->访问指针指向的结构成员
p->num=10;

在使用结构指针访问结构成员时,通常使用指向运算符->

结构指针作为函数参数

int score (struct student *p,int n,int num,int course,int score);

其调用语句

pos=score(students,n,num,course,score);

对应的实参是结构数组名students

PAT (Basic Level) Practice (中文)1003 我要通过!

1003 我要通过! (20 分)

答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件,系统就输出“答案正确”,否则输出“答案错误”。

得到“答案正确”的条件是:

  1. 字符串中必须仅有 PAT这三种字符,不可以包含其它字符;
  2. 任意形如 xPATx 的字符串都可以获得“答案正确”,其中 x 或者是空字符串,或者是仅由字母 A 组成的字符串;
  3. 如果 aPbTc 是正确的,那么 aPbATca 也是正确的,其中 abc 均或者是空字符串,或者是仅由字母 A 组成的字符串。

现在就请你为 PAT 写一个自动裁判程序,判定哪些字符串是可以获得“答案正确”的。

输入格式:

每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (<10),是需要检测的字符串个数。接下来每个字符串占一行,字符串长度不超过 100,且不包含空格。

输出格式:

每个字符串的检测结果占一行,如果该字符串可以获得“答案正确”,则输出 YES,否则输出 NO

输入样例:

8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA

输出样例:

YES
YES
YES
YES
NO
NO
NO
NO
#include<stdio.h>
#include<string.h>
int main()
{
	int n,i;
	char s1[100];
	int count=0,j=0,k=0,num1,num2,num3,num;
	int a[20]={0}; 
	
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		count=0;num1=0;num2=0;num3=0;num=0; 
		scanf("%s",&s1); 
		for(j=0;j<=strlen(s1);j++)
		{
			if(s1[j]=='A'||s1[j]=='P'||s1[j]=='T')
			{
				count++;	
			}
		}
		for(j=0;j<=strlen(s1);j++)
		{
			if(s1[j]=='A')
			{
				num++;	
			}
		}
		j=0;
		while(s1[j++]!='P')
		{
			num1++;	
		}
		while(s1[j++]!='T')
		{
			num2++;
		}
		num3=strlen(s1)-num1-num2-2;
		if(count==strlen(s1)&&count>=3)
		{
			if(num3==num1*num2)
				a[k++]=1;
			else if(s1[0]=='P'&&s1[strlen(s1)-1]=='T'&&num==count-2)
				a[k++]=1;
			else
				a[k++]=0;
		}
		else
			a[k++]=0;
	}
	for(i=0;i<k;i++)
	{
		if(a[i]==1)
		printf("YES\n");
		else
		printf("NO\n");	
	}
}

个人认为这道题最难的就是对题目的理解,以下是我个人对于题目的分析:

如果 aPbTc 正确,则 aPbATca 正确

如果PAT(a=NULL,b=A,c=NULL)正确,则PAAT,PAAAT,PAAAAT等都正确。

如果APATA(a=A,b=A,c=A)正确,则APAATAA,APAAATAAA,APAAAATAAAA等都正确。

如果PATA(a=NULL,b=A,c=A)正确,则PAATA,PAAATA,PAAAATA等都正确。//这种情况不可能发生,因为“任意形如 xPATx 的字符串都可以获得’答案正确‘”。

如果APAT(a=A,b=A,c=NULL)正确,则APAATA,APAAATAA,APAAAATAAA等都是正确的。//这种情况不可能发生,因为”任意形如 xPATx 的字符串都可以获得’答案正确’

指针,数组和地址间的关系

联系:数组名本身是一个地址即指针值

区别:指针是以地址为值的变量,而数组名的值的值是一个特殊的固定地址,可以把它看作是指针常量。

例1

int a[40],*p;

系统分别把编号为3000,3004,3008等的内存字节作为数组元素a[0],a[1],a[2]等的地址(假设int型变量的长度是4个字节)。其中内存位置3000是数组a的基地址,也是a[0]的地址。

例2

假设a[0]的地址为3000,int类型变量的长度为4字节。

p=a;
p=&a[0];

它们都把3000这个地址赋给了指针p。

p=a+1;
p=&a[1];

它们都把3004这个地址赋给了指针p。

例3

设已对a的数组元素进行了赋值

数组求和法一
sum=0;
for(p=a;p<=&a[99];p++)
    num+=*p;

在循环中,指针变量p的初值是数组a的基地址,p连续取值&a[0],&a[1],&a[2]等。

数组求和法二
sum=0;
for(i-0;i<100;i++)
     sum+=*(a+1);

*[a+i]与a[i]等价,*[p+i]与p[i]等价。

数组求和法三
p=a;
sum=0;
for(i=0;i<100;++i) 
   sum+=p[i];

数组名可以使用指针形式,而指针变量也可以使用转换为数组形式。

 

 

PAT (Basic Level) Practice (中文)1002 写出这个数

读入一个正整数 n,计算其各位数字之和,用汉语拼音写出和的每一位数字。

输入格式:

每个测试输入包含 1 个测试用例,即给出自然数 n 的值。这里保证 n 小于 10100

输出格式:

在一行内输出 n 的各位数字之和的每一位,拼音数字间有 1 空格,但一行中最后一个拼音数字后没有空格。

输入样例:

1234567890987654321123456789

输出样例:

程序示例:
#include<stdio.h>
#include<string.h>
int main()
{
	int a[20];
	int sum=0,i=0;
	char s1[101];
	/*计算各数位之和*/
	gets(s1);
	while(s1[i]!='\0')
	{
		sum+=s1[i]-'0';
		i++;
	}	
	i=0;
	while(sum)
	{
		a[i++]=sum%10;
		sum=sum/10;
	}
	/*数字转化为拼音*/
	for(i=i-1;i>0;i--)
	{
		switch(a[i])
		{
			case 0:printf("ling ");break;
			case 1:printf("yi ");break;
			case 2:printf("er ");break;
			case 3:printf("san ");break;
			case 4:printf("si ");break;
			case 5:printf("wu ");break;
			case 6:printf("liu ");break;
			case 7:printf("qi ");break;
			case 8:printf("ba ");break;
			case 9:printf("jiu ");break;
		}
	}
	/*一行中最后一个拼音数字后没有空格*/
	switch(a[0])
	{
		case 0:printf("ling");break;
		case 1:printf("yi");break;
		case 2:printf("er");break;
		case 3:printf("san");break;
		case 4:printf("si");break;
		case 5:printf("wu");break;
		case 6:printf("liu");break;
		case 7:printf("qi");break;
		case 8:printf("ba");break;
		case 9:printf("jiu");break;
	}
	return 0;
}

做这个起初的想法是定义一个整型的n存储输入的数字,后来发现输入数位较大,改用字符串存储,通过s1[i]-‘0’将字符型化为整型。 对于如何使一行中最后一个拼音数字后没有空格,想了好久没有想到什么好主意,只能把最后一项单独拿出来进行考虑。