首页 > 代码库 > 蓝桥杯-带分数
蓝桥杯-带分数
问题描述100 可以表示为带分数的形式：100 = 3 + 69258 / 714。还可以表示为：100 = 82 + 3546 / 197。注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。类似这样的带分数，100 有 11 种表示法。输入格式从标准输入读入一个正整数N (N<1000*1000)输出格式程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。注意：不要求输出每个表示，只统计有多少表示法！样例输入1100样例输出111样例输入2105样例输出26
解题分析：
100 = 82 + 3546 / 197
num = left + up / down
分两步遍历,先遍历left,再遍历down，up = (num - left) * down
然后再验证up是不是符合条件。
注意到数字不允许重复，还不允许出现0，可以使用下面的函数检测，并返回当前数的长度
int is_same_num(int num, int *len){ int i,t; do{ t = num %10; if(t == 0) { return TRUE; } table[t] ++; (*len) ++; }while(num /= 10); for(i = 1; i < 10; i++) { if(table[i] > 1) { return TRUE; } } return FALSE;}
完整代码如下：
#include <stdio.h>#include <stdlib.h>#include <string.h>#define TRUE 1#define FALSE 0char table[10];char backup_table[10];int is_same_num(int num, int *len){ int i,t; do{ t = num %10; if(t == 0) { return TRUE; } table[t] ++; (*len) ++; }while(num /= 10); for(i = 1; i < 10; i++) { if(table[i] > 1) { return TRUE; } } return FALSE;}int main(){ int num,left,up,down,cnt = 0,len = 0; int backup; scanf("%d", &num); for(left = 1; left < num; left++) { len = 0; memset(table, 0, 10); if(is_same_num(left, &len)) { continue; } backup = len; memcpy(backup_table, table, 10); for(down = 1; down < 1e5; down++) { len = 0; memcpy(table, backup_table, 10); if(is_same_num(down, &len)) { continue; } up = (num - left) * down; if(is_same_num(up, &len)) { continue; } if(len + backup == 9) { cnt ++; //printf("%d:%d = %d + %d/%d\n", cnt, num, left, up, down); } } } printf("%d", cnt); return 0;}
蓝桥杯-带分数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。