任何自然数都能用包含「1、1、4、5、1、4」这 6 个数字的式子表示吗？ 第1页
1
Frigus27 网友的相关建议:
upd：证明有点问题，改了一下，对不起大家，我什么都会做的（悲
感谢大家的修正！ありがとナス！
完全可以。事实上，就算只用初等的数学记号，我们也完全可以将任何自然数只用这六个数字表示出来。我个人喜欢将它称作
田所引理（Tadokoro's Lemma）任意自然数可只用“1、1、4、5、1、4”及对数、根号、加号、减号表示。
证明 注意到对任意自然数 ，我们有
将其中的三个 分别用 ， ， 5＋1－4，可得
（绝望）
顺便，由这个定理，我们可以推得以下的定理：
下北沢第一定理（Shimokitazawa's First Theorem， 简记为dssq定律 (Law of DSSQ)） 一切物质皆为野兽先辈（绝望）
证明 不妨设这个物质有英文名（如果没有英文名但有名字，则将其名字读音用拉丁字母表示作为英文名；如果连名字都没有，就随便给它起个名（错乱））那么
- 每个英文字母都有其唯一的ASCII编号
- 因此该英文名可以用其对应的ASCII编号表示
- 每个ASCII编号都是8位二进制数，二进制数前面可以保留0
- 因此将这些二进制数从头到尾拼起来，可以得到一个很长的数字
- 将这个数字转化为十进制数，则每个名字可以唯一对应一个十进制数，我们称其为这个名字的“特征值（eigenvalue）”
- 由田所引理，任意一个特征值可只用“1、1、4、5、1、4”及根号、加号、减号表示
- 结合特征值的唯一确定性，可知该英文名可以如此表示
- 因此，该物质可以这样表示
- 于是，该物质可以被数字论证，故它是野兽先辈（绝望）
（噔噔咚）
那么现在，无论你我，无论花草树朩，都已经被数字论证为野兽先辈了。这，不正是好时代骂！
好时代，来临罢！
以上（悲なしいな）
lcyfrog 网友的相关建议:
全自动数字论证机（迫真）
不知道大家有没有看过《诗云》？既然无法想到某些表示法，那么就把所有的可能列出来罢！（狂喜）
众所周知，OIer都事HOMO。本小鬼在以前暑假集训无聊的时候刚好写过一个数字论证搜索。幸运的是，只用1，1，4，5，1，4排列+括号+加减乘除幂阶乘所能表示的所有可能也就是一个G左右，筛选之后更是只有1.3M，我们就可以很快地查询力
由于python我没怎么用过，所以还是用的c++写的，并且事在晚上订正完考试写的，所以稍微有些麻烦。
以下是代码，想看效果的请直接跳到最后，谢谢茄子！
数据库生成
大体思路就事生成一个排列，然后通过现成的计算器生成答案并且保存。
生成排列
dfs即可。代码如下，主要用栈模拟
#include<iostream> #include<cstdio> #include<algorithm> #include<ctime> #include<cstdlib> #include<stack> #include<cstring> #include<cmath> #include<windows.h> #pragma -g -std=c++11 using namespace std; int t=0; const int num[7]={0,1,1,4,5,1,4}; char s[10]={0,'+','-','*','/','^','!'}; const int mulj[4][7]={{0,0,0,0,0,0,0},{0,1,1,2,1,1,2},{0,0,0,4,2,0,4},{0,0,0,0,0,0,0}}; const int lenj[7]={0,1,1,2,3,1,2}; string ss; int maxn=0; int numb=0; stack<char>ans; const int MAX = 30; const int DONE = 1; //栈定义 template <class T> class Stack{ public: Stack(int MaxStackSize=10); ~Stack() { delete [] stack;} bool IsEmpty() const {return top==-1;} bool IsFull() const {return top==MaxTop;} T Top() const; Stack<T>& Add(const T& x); Stack<T>& Del(T& x); void MakeEmpty(){top=-1;} //清空栈 void print(){ for(int i; i < top + 1; i ++){ cout<<stack[i]<<' '; } cout<<endl; } private: int top;//栈顶 int MaxTop;//最大的栈顶值 T *stack;//堆栈元素数组 }; template<class T> Stack<T>::Stack(int MaxStackSize){ MaxTop=MaxStackSize-1; stack=new T[MaxStackSize]; top=-1; } template<class T> Stack<T>& Stack<T>::Add(const T& x){ if(IsFull()) {cout<<"no memory;"<<endl;return *this;} top=top+1; stack[top]=x; return *this; } template<class T> Stack<T>& Stack<T>::Del(T& x){ if(IsEmpty()) {cout<<"no element"<<endl;return *this;} x=stack[top]; top=top-1; return *this; } template<class T> T Stack<T>::Top() const{ return stack[top]; } //判断一个字符是否为数字 bool isNum(char c){ if((c > '0'||c == '0')&&(c < '9'||c == '9')) return true; else return false; } //删除字符串中的空格 void deleteBlank(string &s){ string::iterator i = s.begin(); while ((i=find(i, s.end(), ' '))!=s.end()) s.erase(i); } //计算器 class Calculator{ public: Calculator(string s); ~Calculator(); int outPriority(char); //返回栈外优先级 int inPriority(char); //返回栈内优先级 bool judgePri(char, char); //判断优先级 前一个为栈外符号，后一个为栈内符号 若前大于后返回1，否则返回0 int judgePri(char); //判断运算符 若是'#'返回 -1，若是')'返回 0，否则返回 1 void dealNum(); //处理数据 int calculate(); //计算 void setString(string const s){ this->s = '#' + s + '#'; deleteBlank(this->s); //删除字符串中的空格 } private: Stack<char> *s_sym; //符号栈 Stack<int> *s_num; //数据栈 string s; }; Calculator::Calculator(string s){ this->s = '#' + s + '#'; deleteBlank(this->s); s_sym = new Stack<char>(MAX); s_num = new Stack<int>(MAX); } Calculator::~Calculator(){ delete s_sym; delete s_num; } int Calculator::outPriority(char symble){ switch(symble){ case '#': return 0; case '(': return 8; case '+': return 2; case '-': return 2; case '*': return 4; case '/': return 4; case '%': return 4; case '^': return 6; case ')': return 1; default: throw 1; } } int Calculator::inPriority(char symble){ switch(symble){ case '#': return 0; case '(': return 1; case '+': return 3; case '-': return 3; case '*': return 5; case '/': return 5; case '%': return 5; case '^': return 7; case ')': return 8; default: throw 1; } } bool Calculator::judgePri(char out, char in){ if(outPriority(out) > inPriority(in)) return true; else return false; } int Calculator::judgePri(char symble){ if(symble == '#') return -1; else if(symble == ')') return 0; else return 1; } void Calculator::dealNum(){ //将数据栈中的前两个弹出进行计算，结果放回数据栈，符号栈弹出顶部元素 char _temp = 0; int dtemp1 = 0; int dtemp2 = 0; s_sym->Del(_temp); s_num->Del(dtemp1); s_num->Del(dtemp2); switch(_temp){ case '+': dtemp2 += dtemp1; break; case '-': dtemp2 = dtemp2 - dtemp1; break; case '*': dtemp2 = dtemp2 * dtemp1; break; case '/': if(dtemp1 == 0) throw 0; else dtemp2 = dtemp2 / dtemp1; break; case '%': dtemp2 = dtemp2 % dtemp1; break; case '^': dtemp2 = pow(dtemp2,dtemp1); break; default: throw 1; } s_num->Add(dtemp2); } int Calculator::calculate(){ for(int i = 0; i < s.size(); i ++){ //遍历字符串 if(isNum(s[i])){ int temp = (int)(s[i]) - 48; //char强制类型转换为int ascii 码数值，减 48 转换为对应整数值 int _temp = 0; if(i > 0 && isNum(s[i - 1])){ s_num->Del(_temp); temp = _temp * 10 + temp; } s_num->Add(temp); }else{ char temp = s[i]; if(s_sym->IsEmpty()){ s_sym->Add(temp); }else{ if(judgePri(temp, s_sym->Top())){ s_sym->Add(temp); }else if(judgePri(temp) == 1){ //栈外优先级小于栈内优先级，且不为 '#' 和 ')' while(!judgePri(temp, s_sym->Top())){ //当栈外优先级比栈内优先级低时，执行栈内符号运算 dealNum(); } s_sym->Add(temp); }else if (judgePri(temp) == -1){ while(s_sym->Top() != '#'){ dealNum(); } int result = s_num->Top(); s_sym->MakeEmpty(); s_num->MakeEmpty(); return result; } else if(judgePri(temp) == 0){ while(s_sym->Top() != '('){ dealNum(); } s_sym->Del(temp); } } } } } char nnans[101]; void exc(){ stack<char>st; while(!ans.empty()){ st.push(ans.top());ans.pop(); } int rs=-1,sta=1,nnn=0; ss=""; while(!st.empty()){ char now=st.top();ans.push(now);st.pop(); ss+=now; } //Calculator c(""); int po=0;int numc=0; for(int i=0;i<ss.length();i++){ if('0'<=ss[i]&&ss[i]<='9'&&!('0'<=ss[i+1]&&ss[i+1]<='9')) nnn++; if(nnn==6) { po = i; break; } } int dd=ss.length(); for(int i=po+1;i<dd;i++) ss.pop_back(); for(int i=0;i<ss.length();i++){ if(ss[i]=='(') numc++; if(ss[i]==')') numc--; } while(numc--) ss+=')'; cout<<ss<<endl; /*c.setString(ss); printf("%d = ",c.calculate()); nnn=0; for(int i=0;i<ss.length();i++){ if(nnn==6&&ss[i]!=')') break; if(ss[i]=='2'&&ss[i+1]=='4'){ printf("4!");i++;nnn++; }else if(ss[i]=='1'&&ss[i+1]=='2'){ printf("5!");i+=2;nnn++; }else if(ss[i]=='('&&ss[i+1]==')'){ i++; }else{ printf("%c",ss[i]);if('1'<=ss[i]&&ss[i]<='9') nnn++; } } putchar(10);*/ } void out(){ stack<char>st; while(!ans.empty()){ //printf("%d
",ans.size()); char sk=ans.top(); st.push(sk);ans.pop(); } while(!st.empty()){ char now=st.top();ans.push(now);st.pop(); printf("%c",now); } putchar(10); Sleep(500); } void dfs(int lev){ if(lev==6){ int tmp=numb; while(numb--){ ans.push(')'); } exc(); numb=tmp; while(tmp--){ ans.pop(); } return; } lev++; for(int i=1;i<=5;i++){ for(int k=1;k<=lenj[lev];k++) ans.push(mulj[k][lev]+'0'); if(lev!=1) ans.push(')'),numb--; ans.push(s[i]); ans.push('('),numb++; //out(); dfs(lev); for(int k=1;k<=lenj[lev];k++) ans.pop(); if(lev!=1) ans.pop(),numb++; ans.pop(); ans.pop(); numb--; ans.push(char(num[lev]+'0')); if(lev!=1) ans.push(')'),numb--; ans.push(s[i]); ans.push('('),numb++; //out(); dfs(lev); if(lev!=1) ans.pop(),numb++; numb--; ans.pop(); ans.pop(); ans.pop(); for(int k=1;k<=lenj[lev];k++) ans.push(mulj[k][lev]+'0'); ans.push(s[i]); ans.push('('),numb++; //out(); dfs(lev); for(int k=1;k<=lenj[lev];k++) ans.pop(); ans.pop(); numb--; ans.pop(); ans.push(num[lev]+'0'); ans.push(s[i]); ans.push('('),numb++; //out(); dfs(lev); ans.pop(); ans.pop(); ans.pop(); numb--; } return; } int main(){ freopen("1.txt","w",stdout); dfs(0); return 0; } 计算答案并输出数据库
去重是一个很重要的问题。用map会RE，我只开了个2e7的桶来简单去重。并且注意到重复一般都聚集在一起（搜索的时候一些相近的生成方案），记录当前答案之前的几个答案即可。
#include <iostream> #include <iomanip> #include <cstdlib> #include <cstring> #include <cctype> #include <cmath> #include <stdio.h> #include <string.h> #include <windows.h> #include<map> using namespace std; const char Tab=0x9; const int DIGIT=1; const int MAXLEN=16384; char s[MAXLEN],*endss; int pcs=15; double fun(double x,char op[],int *iop) { while (op[*iop-1]<32) //本行使得函数嵌套调用时不必加括号,如 arc sin(sin(1.234)) 只需键入arc sin sin 1.234<Enter> switch (op[*iop-1]) { case 7: x=sin(x); (*iop)--;break; case 8: x=cos(x); (*iop)--;break; case 9: x=tan(x); (*iop)--;break; case 10: x=sqrt(x); (*iop)--;break; case 11: x=asin(x); (*iop)--;break; case 12: x=acos(x); (*iop)--;break; case 13: x=atan(x); (*iop)--;break; case 14: x=log10(x);(*iop)--;break; case 15: x=log(x); (*iop)--;break; case 16: x=exp(x); (*iop)--;break; } return x; } double calc(char *expr,char **addr) { static int deep; //递归深度 static char *fname[]={ "sin","cos","tan","sqrt","arcsin","arccos","arctan","lg","ln","exp",NULL}; double ST[10]={0.0}; //数字栈 char op[10]={'+'}; //运算符栈 char c,*rexp,*pp,*pf; int ist=1,iop=1,last,i; if (!deep) { pp=pf=expr; do { c = *pp++; if (c!=' '&& c!=Tab) *pf++ = c; } while (c!=' '); } pp=expr; if ((c=*pp)=='-'||c=='+') { op[0] = c; pp++; } last = !DIGIT; while ((c=*pp)!=' ') { if (c=='(') {//左圆括弧 deep++; ST[ist++]=calc(++pp,addr); deep--; ST[ist-1]=fun(ST[ist-1],op,&iop); pp = *addr; last = DIGIT; if (*pp == '('||isalpha(*pp) && strnicmp(pp,"Pi",2)) {//目的是：当右圆括弧的右恻为左圆括弧或函数名字时，默认其为乘法 op[iop++]='*'; last = !DIGIT; c = op[--iop]; goto operate ; } } else if (c==')') {//右圆括弧 pp++; break; } else if (isalpha(c)) { if (!strnicmp(pp,"Pi",2)) { if (last==DIGIT) { return -1; } ST[ist++]=3.14159265358979323846264338328; ST[ist-1]=fun(ST[ist-1],op,&iop); pp += 2; last = DIGIT; if (!strnicmp(pp,"Pi",2)) { return -1; } if (*pp=='(') { return -1; } } else { for (i=0; (pf=fname[i])!=NULL; i++) if (!strnicmp(pp,pf,strlen(pf))) break; if (pf!=NULL) { op[iop++] = 07+i; pp += strlen(pf); } else { return -1; } } } else if (c=='+'||c=='-'||c=='*'||c=='/'||c=='^') { char cc; if (last != DIGIT) { return -1; } pp++; if (c=='+'||c=='-') { do { cc = op[--iop]; --ist; switch (cc) { case '+': ST[ist-1] += ST[ist];break; case '-': ST[ist-1] -= ST[ist];break; case '*': ST[ist-1] *= ST[ist];break; case '/': ST[ist-1] /= ST[ist];break; case '^': ST[ist-1] = pow(ST[ist-1],ST[ist]);break; } } while (iop); op[iop++] = c; } else if (c=='*'||c=='/') { operate: cc = op[iop-1]; if (cc=='+'||cc=='-') { op[iop++] = c; } else { --ist; op[iop-1] = c; switch (cc) { case '*': ST[ist-1] *= ST[ist];break; case '/': ST[ist-1] /= ST[ist];break; case '^': ST[ist-1] = pow(ST[ist-1],ST[ist]);break; } } } else { cc = op[iop-1]; if (cc=='^') { return -1; } op[iop++] = c; } last = !DIGIT; } else { if (last == DIGIT) { return -1; } ST[ist++]=strtod(pp,&rexp); ST[ist-1]=fun(ST[ist-1],op,&iop); if (pp == rexp) { return -1; } pp = rexp; last = DIGIT; if (*pp == '('||isalpha(*pp)) { op[iop++]='*'; last = !DIGIT; c = op[--iop]; goto operate ; } } } *addr=pp; if (iop>=ist) { exit(0); } while (iop) { --ist; switch (op[--iop]) { case '+': ST[ist-1] += ST[ist];break; case '-': ST[ist-1] -= ST[ist];break; case '*': ST[ist-1] *= ST[ist];break; case '/': ST[ist-1] /= ST[ist];break; case '^': ST[ist-1] = pow(ST[ist-1],ST[ist]);break; } } return ST[0]; } int mp[20000000]; long long pr1=-114514,pr2=-1919810; int main() { freopen("1.txt","r",stdin); freopen("senpai_database.txt","w",stdout); while (1) { gets(s); double resu=calc(s,&endss);if(resu==-1||resu<0||(resu-floor(resu)>0)||(resu<=2e7&&(mp[int(resu)]))){ continue; }else if(((long long)resu==pr1)||((long long)resu==pr2)){ pr2=pr1,pr1=(long long)(resu);continue; } if(resu<=2e7) mp[(int)resu]=1; printf("%lld = ",(long long)resu); long long nnn=0,cntt=0; int nn=strlen(s); for(long long i=0;i<nn;i++){ if(nnn==6&&s[i]!=')') break; if(s[i]=='2'&&s[i+1]=='4'){ printf("4!");i++;nnn++; }else if(s[i]=='1'&&s[i+1]=='2'){ printf("5!");i+=2;nnn++; }else{ printf("%c",s[i]);if('1'<=s[i]&&s[i]<='9') nnn++; } if(s[i]=='(') cntt++; if(s[i]==')') cntt--; } while(cntt--){ printf(")"); } putchar(10); pr2=pr1,pr1=(long long)(resu); } return 0; } 查询数据库
如果能排序二分的话能省不少时间，但是数据量太大了没法排序，我就直接FOR过去了。实测字母少的时候很快。
#include <iostream> #include <string> #include <algorithm> #include <cmath> #include<cstring> using namespace std; int tt=0; char t[1001]; int main() { //freopen("1.txt","r",stdin); scanf("%s",t); freopen("senpai_database.txt","r",stdin); //freopen("out.txt","w",stdout); char s[1001]; int li=strlen(t); int key=0; for(int i=0;i<li;i++){ printf("%c",t[i]); } printf(" = "); for(int i=0;i<li;i++){ int p=t[i]-'a'+1>0?t[i]-'a'+1:t[i]-'0'; if(li!=1) printf("%d",p); if(i<li-1) printf("+"); key+=p; } if(li!=1) printf(" = ");//return 0; while(gets(s)){ int res=0,pos=0,ll=strlen(s); while(isdigit(s[pos])&&pos<ll){ res=(res<<1)+(res<<3)+s[pos++]-'0'; } if(s[0]==0) return 0; if(key==res){ for(int i=0;i<ll;i++){ printf("%c",s[i]); } return 0; } s[0]=0; } return 0; } 用法：直接输入字母，如下
如果想要自己尝试请依次编译运行上面三个，不过耗时会有点久，还占内存（悲）
其实还有更高级的运算可能，有些数字也还没表示出来，不过大部分都可以，并且我急着要去和朋友晒一发，就没有写 （✝你改悔罢✝）
1
相关话题
这个数学问题有解吗，有哪些好的处理思路？如何证明这个复变函数列的一致收敛性？
为什么有那么多人不承认0.9无限循环=1，且振振有词？
如何通过卫星图判断这架飞机距离地面的高度？
从自然数 1 ~ n 中随机取 m（1≤m≤n）个，其中最大数的数学期望是多少？
高斯素数有类似于素数定理的分布律吗？
假设我扔一枚硬币，60次有55次正面朝上，我有多大把握认为这枚硬币正面和反面出现概率不相同？
为什么该图形红蓝面积相等?
数学这门学科真的重要吗？
如何制作一个πΩ的电阻，并尽可能精确?
相关的话题
数列an（定义an为71^n）是否在an中能找到以任意长度（不小于1）个1为结尾的数（均是正整数）?理想细绳随机切为n段，为什么最短段长度的期望为原长的1/n²？
如何判断一个超级大的数是不是素数？
有哪些令人为之惊叹的数学题目？
如何评价数学家张益唐？
一周学完初中三年所有知识可能吗？
高中生能独自推导出 π 的计算公式是什么水平？
如果从图中移去一个边的一个集合将增加亚图的数目时，被移去的边的集合就成为截。”那么，亚图是什么？截呢？
如何直观地解释「紧致性」？
英国人真的连乘法口诀都不熟悉么？
这个式子对吗？若是，具体步骤是什么？
√3 大约是多少？该如何计算？
当我们说一个定理可以推出另一个定理的时候, 我们在说什么?
有哪些具有特殊性质的数字？
10个人各自从1-10选数字，尽量让自己最大且不重复，如何选？
高中数学有无学习的必要？
请问以下两个概率问题的答案是否一样？
如何证明下面的整除关系成立？
有哪些形式简单却很难证明的不等式？
整数多还是偶数多？
integral domain为啥叫整环？
质数集P与自然数集N等势吗?
这张图中能数出多少个三角形？
李煌的阶乘计算小技巧，与斯特林公式有什么区别？
如何估计如下的无穷积分不等式？
如何构造 [0,1] * [0,1] 到 [0,1] 的双射 ?
不同国家和制度的数学PhD成才率（永久学术职位）是多少？有多大差别？
数学为什么需要证明一些看起来非常直观、明显的东西（比如定理）？
怎样理解一个非常大的数？
如何看待微博刘大可先生与万精油微博之争？