KeyFansClub
凌波然 - 2005/11/20 13:42:00
信息学奥赛复赛结束!庆祝一下.
我参加的是普及组,这次的题目好简单,比前几届简单多了,提高组好像也是这样。我做出三道题目,第四道题目虽然有思路,程序也打出来了,不过就是不对,希望这次成绩能好一点。
题目大致如下:求一个正整数n的正整数次幂的后k位是否会发生循环?如果
是,最短循环长度是多少?(1<k<=100)输出循环长度,若不存在,输出-1
同祝大家成绩优秀。
[IMG=upload/KFCFile7164_edo2.jpg]上传文件7164[/IMG]
神奈备命 - 2005/11/20 13:49:00
祝愿楼主取得好成绩啊~~~~
某也只能说这个了...关于"信息学奥赛".....连名字都米听过....
←---某小白飘过...
Miliardo - 2005/11/20 13:52:00
某素提高组……
RP爆发爆发了220分……
不过省队就断念了……
碇 - 2005/11/20 14:00:00
楼主好强= =
也不知道“信息学奥赛”
而且发现……我不会算……zro
K<100的,而且只要最短循环长度……似乎可以来穷举的?
好奇= =
问下,用什么语言?循环是指从末位算么,如123123算是循环而1231237不算什么的?
千叶奈奈 - 2005/11/20 14:33:00
然姐姐参加的复赛结束了?那么先祝贺一下...
实话说奈奈数学烂烂的||||所以那道谜题看了半天貌似也做不出来 = = 也没法给姐姐什么帮助 面壁...
总之希望姐姐能进决赛 也不要太辛苦了哟^^
幻蓝飘羽 - 2005/11/20 14:35:00
信息学奥赛复赛????信息学????楼主来阐释一下吧~~~~
粘土火星 - 2005/11/20 14:50:00
以下引用Miliardo在2005-11-20 13:52:36的发言: 某素提高组…… RP爆发爆发了220分…… 不过省队就断念了…… |
话说去年230分来着-___________-b
提高组如果比去年还简单我可以去死了……
PS:楼主的题N有范围么?
碇 - 2005/11/20 15:13:00
以下引用神奈の无奈在2005-11-20 14:33:48的发言: 实话说奈奈数学烂烂的||||所以那道谜题看了半天貌似也做不出来 = = |
这是正常的,我看着不太像是能用数学解决的= = 或者我实在太废了
唔,因为不知道K位内有循环的具体定义(算压缩算法?还是纯粹严格的循环?)7123123123这样算是有循环不?1231231237这样呢?
我是废人,试着用C写严格循环(123123123)的吧……zro
Miliardo - 2005/11/20 15:15:00
以下引用粘土火星在2005-11-20 14:50:46的发言:
话说去年230分来着-___________-b
提高组如果比去年还简单我可以去死了……
PS:楼主的题N有范围么? |
去年提高组的题目……简单到渣……
可惜某去年初赛挂掉了……T_T……
今年貌似难到出题人被诅咒……详情请见OIBH……Orz……
粘土火星 - 2005/11/20 15:18:00
循环的样例……楼主没提供= =b
话说这题,时间大概耗在维护高精度上……
碇 - 2005/11/20 15:25:00
以下引用粘土火星在2005-11-20 15:18:53的发言: 话说这题,时间大概耗在维护高精度上…… |
唔
“正整数n的正整数次幂”
突然想到,我为什么会觉得是C呢……难道被虐待习惯了(一般考算法什么都会跑到C上考……)数字向字符串转换都要自己来……zro
粘土火星 - 2005/11/20 15:27:00
以下引用Miliardo在2005-11-20 15:15:54的发言:
去年提高组的题目……简单到渣…… 可惜某去年初赛挂掉了……T_T……
今年貌似难到出题人被诅咒……详情请见OIBH……Orz…… |
那么先恭喜阁下=v=???去年的渣题咱的分数也没阁下多哼哼哼,大概一辈子会和低级错误沾边了
PS:综上所述和OI有关的WEB SITE和某已经无缘=v=b,也算是种解脱咯
PS:不要再出现比前年还低的分数吧-_-b 80太寒了
LOVEHINA-AVC - 2005/11/20 15:53:00
题目都没有看懂orz
LOVEHINA-AVC - 2005/11/20 19:04:00
吃完饭后试了一下,不知道对题意有没理解错误-_-d
[strike]由于偶不熟悉C和PASCAL(爆),以下源码各位请54……[/strike]
.386
.model flat,stdcall
option casemap:none
include \masm32\include\kernel32.inc
includelib \masm32\lib\kernel32.lib
include \masm32\include\user32.inc
includelib \masm32\lib\user32.lib
.DATA
szSignedFormat db "%d",0
szUnsignedFormat db "%u",0
.CODE
start:
push 4 ;Power
push 100 ;Base
call GetCycle
mov ebp,esp
push eax
push OFFSET szSignedFormat
push ebp
call wsprintf
add esp,12
mov ebp,esp
push 0
push ebp
push ebp
push 0
call MessageBox
push 0
call ExitProcess
GetCycle proc stdcall
mov eax,[esp + 4]
mov ebx,eax
mov ecx,[esp + 8]
dec ecx
sub esp,104
mov ebp,esp
and DWORD PTR[ebp + 100],0
@@:
xor edx,edx
mul ebx
jo Overflow
dec ecx
jnz @b
@@:
push eax
push eax
push OFFSET szUnsignedFormat
push ebp
call wsprintf
add esp,12
pop eax
xor ecx,ecx
@@:
inc ecx
mov bl,[esp + ecx]
test bl,bl
jz @f
mov [esp + ecx - 1],bl
jmp @b
@@:
dec ecx
cmp ecx,100
ja NotFound
xor esi,esi
inc esi
CompareStringStart:
mov edi,esi
CompareStringLoop:
xor ebp,ebp
@@:
mov bl,[esp + ebp]
add edi,ebp
cmp edi,ecx
je NotMatch
mov dl,[esp + edi]
sub edi,ebp
cmp bl,dl
jne NotMatch
inc ebp
cmp ebp,esi
jne @b
add edi,esi
cmp edi,ecx
jb CompareStringLoop
FullyMatched:
mov [esp + 100],esi
NotMatch:
inc esi
mov edx,ecx
shr edx,1
cmp esi,edx
jbe CompareStringStart
cmp DWORD PTR[esp + 100],0
je NotFound
xor edx,edx
mov eax,ecx
mov ecx,[esp + 100]
div ecx
EndOfProc:
add esp,104
ret 8
Overflow:
NotFound:
xor eax,eax
dec eax
jmp EndOfProc
GetCycle endp
end start
编译选项:
ml /c /coff /nologo GetCycle.asm
link /subsystem:windows /libpath:\masm32\lib /nologo GetCycle.obj
很懒就没有做参数录入了,不知道比赛的话这样会不会扣分?
另外精度是个问题……完整的应该要采用浮点寄存器Orz
碇 - 2005/11/20 19:14:00
#include "string.h"
int cycle(int n,int s,int k){ char x[101],q[101],w[101]; int i=0,j,l,m=0,r,o,p=0; unsigned long a=1;
for(j=0;j<s;j++) a*=(unsigned long)n; printf("%ld\n",a);
while(a) { x=a-a/10*10+48; a=a/10; i++; } x=0;
if(i>k) i=k;
for(j=0;j<i/2;j++) {r=i/(j+1); if (i%(j+1)) continue;
for(l=0;l<=j;l++) { q[l]=x[m]; m++; } q[l]=0;
for(o=0;o<r-2;o++) { for(l=0;l<=j;l++) { w[l]=x[m]; m++; } w[l]=0; if(strcmp(q,w)) {p=1; break;}}
if(p) continue; printf("%d\n\n",j); return (j); } if(p) printf("-1\n\n"); return (-1); }
main(){ int cycle(int n,int s,int k); int n,s,k=101; while(k>100||k<1){ printf("input the number as n s k and k<100\n"); scanf("%d%d%d",&n,&s,&k);} cycle(n,s,k); } |
呃,战完……好乱,请各位指错(有循环的怎么没发现……全是-1- -||||)
请无视诸如变量命名不规范,提示不友好,计算位数有限(特别是第二个参数),乱什么的……
LOVEHINA-AVC - 2005/11/20 19:25:00
爆,我把K给忘了(直接去掉第一位)……
LOVEHINA-AVC - 2005/11/20 20:46:00
对了要调试着看的话可以用下面的编译选项:
ml /c /coff /Zi /nologo GetCycle.asm
link /debug /debugtype:CV /subsystem:windows /libpath:\masm32\lib /nologo GetCycle.obj
然后直接用OllyDbg加载就可以进行源码级调试了-v-b
(众:需要吗?你都没有用命名变量)
希德船长 - 2005/11/20 21:03:00
“正整数n的正整数次幂”,用C来生成的话,就算用unsigned long 格式的数字,最大才10位,绝对不会有100位尾数的。除非自己写一个无穷位乘法器来生成结果,再进行搜索判断。
我来试试。。。。。。
碇 - 2005/11/20 21:17:00
所以汇编容易做的厚道点吧= =
不然就战去吧……应该也有办法= =
LOVEHINA-AVC - 2005/11/20 21:27:00
比赛不可能用汇编伐,源码量&调试难度跟C/PASCAL相比不是一个级别的=_=
C我只能用来写驱动,做数学题还是PASCAL容易啊,继续看PASCAL基础去……
PS:问一下,楼上的战是啥意思?
碇 - 2005/11/20 21:38:00
希德船长君要战C下面的无穷位乘法器= =
我觉得这其实比题目本身要繁……
动态分配内存全拆成1个单位的位段来?
……
还是写汇编好了- -|||||||
其实这两个我都不熟……破解及邪恶程序爱好者可能会比较清楚
C也一年没摸了……
LOVEHINA-AVC - 2005/11/20 21:54:00
越看越不像是NOIP的题目
至于那个无穷位乘法计算器……[strike]来跟踪一下WINDOWS的calc[/strike]
Miliardo - 2005/11/20 22:02:00
以下引用凌波然在2005-11-20 13:42:12的发言: 信息学奥赛复赛结束!庆祝一下. 我参加的是普及组,这次的题目好简单,比前几届简单多了,提高组好像也是这样。我做出三道题目,第四道题目虽然有思路,程序也打出来了,不过就是不对,希望这次成绩能好一点。
题目大致如下:求一个正整数n的正整数次幂的后k位是否会发生循环?如果 是,最短循环长度是多少?(1<k<=100)输出循环长度,若不存在,输出-1
同祝大家成绩优秀。 [IMG=upload/KFCFile7164_edo2.jpg]上传文件7164[/IMG]
|
普及组某也不素很清楚……
提高组难度相当BT……
希德船长 - 2005/11/20 22:36:00
无穷位乘法器完成。
按输入输出的是字符串来处理,数字的话则转换后再使用。
这么做比较浪费内存空间,但是便于输出。
int MulFunction(char *Input1, char *Input2, char *Output)
{
int NumLenInput1,NumLenInput2, i, j;
//判断数字长度
for(i=0;;i++)
{
if(Input1 < 48 || Input1 > 57)
{
NumLenInput1 = i;
break;
}
Input1 -= 48;
}
for(i=0;;i++)
{
if(Input2 < 48 || Input2 > 57)
{
NumLenInput2 = i;
break;
}
Input2 -= 48;
}
//若Output == NULL则将结果所需的长度用返回值告知使用者
if(Output == NULL)
return NumLenInput1+NumLenInput2;
//初始化结果字符串
for(i=NumLenInput1+NumLenInput2-1; i>=0; i--)
Output = 0;
Output[NumLenInput1+NumLenInput2] = '\0';
//乘
for(i=0; i<NumLenInput2; i++)
{
for(j=0; j<NumLenInput1; j++)
Output[NumLenInput1+NumLenInput2-1-i-j] += Input1[NumLenInput1-1-j]*Input2[NumLenInput2-1-i];
for(j=NumLenInput1+NumLenInput2-1; j>=0; j--)
{
if(Output[j] > 9)
{
Output[j-1] += Output[j]/10;
Output[j] %= 10;
}
}
}
//将结果转换为字符串
for(i=0; i<NumLenInput1+NumLenInput2; i++)
Output += 48;
for(i=0; i<NumLenInput1; i++)
Input1 += 48;
for(i=0; i<NumLenInput2; i++)
Input2 += 48;
//返回结果字符串的最大长度。
return NumLenInput1+NumLenInput2;
}
碇 - 2005/11/20 23:28:00
唔唔唔
出来了么= =
用字符串来么
"int Temp10;"
传说C定义和高级语言不一样一定要放函数开头?
for(i=0;;i++) { if(Input1 < 48 || Input1 > 57) { NumLenInput1 = i; break; } |
这样NumLenInput1 NumLenInput1都会比数组的数据部分多1 所以Output数组要按减2来算?(这人就是喜欢说数组-v-)
zro……请无视
那么,谁来做修改整合工作捏-v-
东南之风 - 2005/11/20 23:29:00
我提高组彻底挂了,反而最简单的第一题天知道哪出问题,居然没出来,靠,自己测的时候都没问题
LOVEHINA-AVC - 2005/11/20 23:34:00
以下引用碇在2005-11-20 23:28:11的发言: 唔唔唔 出来了么= = 用字符串来么 "int Temp10;" 传说C定义和高级语言不一样一定要放函数开头?
|
因为那个要对应
push ebp
mov ebp,esp
sub esp,XXX(add esp,-XXX)
在进入函数区块后首先进行局部变量栈空间的划分
PS:C也是高级语言
碇 - 2005/11/20 23:39:00
唔
那超高级语言好了-v-
希德船长 - 2005/11/21 13:01:00
其实我上面那函数是在C++下写的。
刚才修正了一下,同时修正了执行后输入字符串被改变的毛病。现在应该可以在C下用了。
本来想把成品(MFC应用程序)传上来,可是这几天我的机器带病毒,万一传上来的东西也带病毒就麻烦了,只能在这里直接贴代码了。
以下为将m_Input的m_Power次幂的结果输出到m_Result里的代码,m_Input,m_Power和m_Result是三个编辑框控件。
void CMulDlg::OnBUTTONMul()
{
// TODO: Add your control notification handler code here
int i;
int NumLength = m_Input.GetWindowTextLength();
char *InputTemp = (char *)malloc(NumLength+1);
m_Input.GetWindowText(InputTemp,NumLength+1);
int PowerLength = m_Power.GetWindowTextLength();
char *PowerTemp = (char *)malloc(PowerLength+1);
m_Power.GetWindowText(PowerTemp,PowerLength+1);
int Power = atoi(PowerTemp);
char *Result = (char *)malloc(NumLength*Power+1);
char *ResultTemp = (char *)malloc(NumLength*Power+1);
if(Power == 0)
strcpy(Result,"1");
else if(Power == 1)
strcpy(Result,InputTemp);
else
{
strcpy(ResultTemp,InputTemp);
for(i=0; i<Power-1; i++)
{
MulFunction(ResultTemp,InputTemp,Result);
strcpy(ResultTemp,Result);
}
for(i=0; i<NumLength*Power+1; i++)
if(ResultTemp != '0')
break;
strcpy(Result,ResultTemp+i);
}
m_Result.SetWindowText(Result);
}
有了字符串格式的结果,下面的匹配搜索就好办了。
凌波然 - 2005/11/21 20:09:00
其实那道题目我也有思路,只不过内存老是溢出,优化不能
而且高精度乘法也比较耗时,估计测试的时候我的程序会超时